How to Solve Two Sum II - Input Array Is Sorted

In this problem, you are tasked with finding two numbers in a sorted array that sum to a target value. By leveraging binary search over the valid answer space, we can quickly find the solution in O(n log n) time or O(n) with two pointers. The key here is to understand how the sorted nature of the array allows us to efficiently locate the correct pair of indices.

Problem Statement

Given a 1-indexed array of integers numbers that is sorted in non-decreasing order, you need to find two numbers such that their sum equals a specific target number. These two numbers are numbers[index1] and numbers[index2], where 1 <= index1 < index2 <= numbers.length.

Your task is to return the indices of the two numbers, index1 and index2, as an integer array of length 2. The tests ensure that there is exactly one solution, and you cannot use the same element twice.

Examples

Example 1

Input: numbers = [2,7,11,15], target = 9

Output: [1,2]

The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2

Input: numbers = [2,3,4], target = 6

Output: [1,3]

The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3

Input: numbers = [-1,0], target = -1

Output: [1,2]

The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

Solution Approach

Two Pointers

By using the two-pointer technique, we place one pointer at the beginning of the array and another at the end. We then check the sum of the numbers at these pointers. If the sum is less than the target, we move the left pointer forward to increase the sum. If the sum is greater than the target, we move the right pointer backward to decrease the sum. This approach runs in O(n) time.

Binary Search

Since the array is sorted, we can apply binary search. For each element, we perform binary search for the complement of the current number (target - number). This reduces the complexity to O(n log n).

Optimization Considerations

Using binary search can offer a significant speedup compared to brute-force approaches, especially for larger arrays. This solution avoids unnecessary checks and efficiently narrows down the possibilities by exploiting the sorted nature of the array.

Complexity Analysis

The two-pointer method works in O(n) time and O(1) space. The binary search method runs in O(n log n) time and O(1) space. Choosing between these approaches depends on the specific trade-offs between time complexity and simplicity of the implementation.

What Interviewers Usually Probe

• Candidates should understand the benefits of applying binary search to a sorted array.
• Look for understanding of the two-pointer technique and when it is most useful.
• The candidate should be able to discuss the space-time trade-offs between the different approaches.

Common Pitfalls or Variants

Common pitfalls

• Failing to recognize that the array is sorted, which leads to inefficient brute-force solutions.
• Not considering edge cases such as negative numbers or arrays with only two elements.
• Mixing up index-based positions with 0-indexed arrays—make sure indices are 1-based.

Follow-up variants

• What if the array is not sorted? The problem would require different approaches like using a hash map.
• How would you solve the problem if there were multiple pairs that sum to the target? You’d need to modify your approach to find all pairs.
• How would this problem change if the array contained repeated elements? You would need to ensure that no element is used more than once.

How GhostInterview Helps

• GhostInterview provides instant explanations of the binary search approach for this problem.
• Our step-by-step solver allows you to experiment with both the two-pointer and binary search methods.
• The solution insights provided help you practice the trade-offs between different approaches under interview conditions.

Topic Pages

• Array
• Two Pointers
• Binary Search

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the best way to solve Two Sum II - Input Array Is Sorted?

The optimal way is to use the two-pointer technique, achieving O(n) time complexity. Alternatively, you can use binary search for O(n log n) time complexity.

Can I solve this problem with brute force?

Yes, but brute force results in O(n^2) time complexity, which is inefficient for larger arrays. A more efficient solution is required for large input sizes.

Why is binary search useful in this problem?

Binary search takes advantage of the sorted nature of the array, enabling faster searching for the complement of each element.

How does the two-pointer technique work here?

The two-pointer technique works by starting with pointers at both ends of the sorted array. You adjust the pointers based on the sum of the elements they point to, ensuring you efficiently find the pair that sums to the target.

What happens if the array is not sorted?

If the array is not sorted, binary search and the two-pointer technique cannot be used. You would likely need to use a hash map or other sorting-based methods.