167. Two Sum II Input Array Is Sorted - Explanation

Description

Given an array of integers numbers that is sorted in non-decreasing order.

Return the indices (1-indexed) of two numbers, [index1, index2], such that they add up to a given target number target and index1 < index2. Note that index1 and index2 cannot be equal, therefore you may not use the same element twice.

There will always be exactly one valid solution.

Your solution must use $O(1)$ additional space.

Example 1:

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

Output: [1,2]

Explanation:
The sum of 1 and 2 is 3. Since we are assuming a 1-indexed array, index1 = 1, index2 = 2. We return [1, 2].

Constraints:

2 <= numbers.length <= 1000
-1000 <= numbers[i] <= 1000
-1000 <= target <= 1000

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Hint 1

A brute force solution would be to check every pair of numbers in the array. This would be an O(n^2) solution. Can you think of a better way?

Hint 2

Can you think of an algorithm by taking the advantage of array being sorted?

Hint 3

We can use the two-pointer algorithm. If nums[0] + nums[n-1] > target, then we know nums[n - 1] can not possibly be included in any pairs. Why? Because nums[n - 1] is the largest element in the array. Even by adding it with nums[0], which is the smallest element, we still exceed the target. You can think of the case when nums[0] + nums[n - 1] < target.

Hint 4

We keep two pointers, one at the start and the other at the end of the array. If the sum of the numbers at the two pointers is greater than the target, decrement the right pointer, else increment the left pointer. Repeat this process until you find a valid pair.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

Brute force ignores the ordering and simply checks every possible pair.
For each index i, we look at every index j > i and check whether their sum equals the target.
This approach is easy to understand but inefficient because it tries all combinations without using the sorted property.

Algorithm

Loop through the array using index i from 0 to n - 1.
For each i, loop through index j from i + 1 to n - 1.
If numbers[i] + numbers[j] equals the target:
- Return [i + 1, j + 1] (1-indexed as required by the problem).
If no such pair is found, return an empty list.

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

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Binary Search

Intuition

Because the array is already sorted, we don’t need to check every pair.
For each number at index i, we know exactly what value we need to find:
target - numbers[i].
Since the array is sorted, we can efficiently search for this value using binary search instead of scanning linearly.
This reduces the inner search from O(n) to O(log n), making the solution much faster.

Algorithm

Loop through each index i from 0 to n - 1.
For each number numbers[i], compute the needed complement:
- tmp = target - numbers[i]
Perform binary search on the subarray from i + 1 to the end:
- If numbers[mid] == tmp, return [i + 1, mid + 1]
- If numbers[mid] < tmp, search the right half
- Otherwise, search the left half
If no pair is found after checking all indices, return an empty list.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            l, r = i + 1, len(numbers) - 1
            tmp = target - numbers[i]
            while l <= r:
                mid = l + (r - l)//2
                if numbers[mid] == tmp:
                    return [i + 1, mid + 1]
                elif numbers[mid] < tmp:
                    l = mid + 1
                else:
                    r = mid - 1
        return []

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$

3. Hash Map

Intuition

Even though the array is sorted, we can still use a hash map to solve the problem efficiently.
As we scan through the list, we compute the needed complement for each number.
If that complement has already been seen earlier (stored in the hash map), then we have found the required pair.
Otherwise, we store the current number with its (1-indexed) position.

Algorithm

Create an empty hash map mp that maps numbers to their 1-indexed positions.
Loop through the array with index i from 0 to n - 1:
- Compute the complement: tmp = target - numbers[i]
- If tmp exists in mp, return [mp[tmp], i + 1]
- Otherwise, store the current number in the map:
  - mp[numbers[i]] = i + 1
If no pair is found, return an empty list.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        mp = defaultdict(int)
        for i in range(len(numbers)):
            tmp = target - numbers[i]
            if mp[tmp]:
                return [mp[tmp], i + 1]
            mp[numbers[i]] = i + 1
        return []

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Two Pointers

Intuition

Because the array is sorted, we can use two pointers to adjust the sum efficiently.
If the current sum is too big, moving the right pointer left makes the sum smaller.
If the sum is too small, moving the left pointer right makes the sum larger.
This lets us quickly close in on the target without checking every pair.

Algorithm

Initialize two pointers:
- l = 0 (start)
- r = len(numbers) - 1 (end)
While l < r:
- Compute curSum = numbers[l] + numbers[r].
- If curSum > target, move r left to reduce the sum.
- If curSum < target, move l right to increase the sum.
- If curSum == target, return [l + 1, r + 1].
If no pair matches the target, return an empty list.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1

        while l < r:
            curSum = numbers[l] + numbers[r]

            if curSum > target:
                r -= 1
            elif curSum < target:
                l += 1
            else:
                return [l + 1, r + 1]
        return []

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Returning 0-Indexed Instead of 1-Indexed Results

The problem explicitly requires 1-indexed positions in the output. A common mistake is returning [i, j] instead of [i + 1, j + 1]. Always double-check the problem requirements for indexing conventions, as returning 0-indexed results will be marked as incorrect.

Not Leveraging the Sorted Property

Since the array is already sorted, the two-pointer approach achieves O(n) time with O(1) space. Using a hash map still works but wastes the sorted property and uses O(n) extra space unnecessarily. While not incorrect, failing to recognize and use the sorted property results in a suboptimal solution.

Moving Both Pointers in the Same Direction

In the two-pointer approach, when the sum is too large you should move the right pointer left, and when the sum is too small you should move the left pointer right. A common error is moving both pointers in the same direction or moving the wrong pointer, which causes the algorithm to miss the valid pair or loop infinitely.