#167

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Two Sum II - Input Array Is Sorted

Solve the Two Sum II problem efficiently using binary search over a valid answer space in a sorted array.

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1: Binary Search

Note that the array is sorted in non-decreasing order, so for each `numbers[i]`, we can find the position of `target - numbers[i]` by binary search, and return $[i + 1, j + 1]$ if it exists.

1

2

3

4

5

6

7

8

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        for i in range(n - 1):
            x = target - numbers[i]
            j = bisect_left(numbers, x, lo=i + 1)
            if j < n and numbers[j] == x:
                return [i + 1, j + 1]

Solution 2: Two Pointers

We define two pointers $i$ and $j$, which point to the first element and the last element of the array respectively. Each time we calculate $numbers[i] + numbers[j]$. If the sum is equal to the target value, return $[i + 1, j + 1]$ directly. If the sum is less than the target value, move $i$ to the right by one position, and if the sum is greater than the target value, move $j$ to the left by one position.

1

2

3

4

5

6

7

8

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        for i in range(n - 1):
            x = target - numbers[i]
            j = bisect_left(numbers, x, lo=i + 1)
            if j < n and numbers[j] == x:
                return [i + 1, j + 1]

Continue Practicing

#287 find the duplicate number #349 intersection of two arrays #350 intersection of two arrays ii