Skip to main content
CodePeetCodePeet
CodePeet 250

Two Sum II - Input Array Is Sorted

MEDIUMProblemSolveExternal Links

Description

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.

Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one (1-indexed) as an integer array [index1, index2] of length 2.

The tests guarantee that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

The key constraint here is that the array is already sorted. Unlike the original Two Sum problem, you should exploit this sorted property to avoid hash maps and achieve better space efficiency.

Examples

Example 1

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

Output: [1, 2]

Explanation: numbers[1] + numbers[2] = 2 + 7 = 9. The pair at positions 1 and 2 (1-indexed) sums to the target. No other pair of distinct indices produces 9.

Example 2

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

Output: [1, 3]

Explanation: numbers[1] + numbers[3] = 2 + 4 = 6. Note that numbers[2] + numbers[2] = 3 + 3 = 6 as well, but we cannot use the same element twice. The valid pair is at indices 1 and 3.

Example 3

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

Output: [1, 2]

Explanation: numbers[1] + numbers[2] = -1 + 0 = -1. This shows the algorithm handles negative numbers correctly. With only two elements, the answer is always [1, 2] if a solution exists.

Constraints

  • 2 ≤ numbers.length ≤ 3 × 10^4
  • -1000 ≤ numbers[i] ≤ 1000
  • numbers is sorted in non-decreasing order
  • -1000 ≤ target ≤ 1000
  • There is exactly one solution

Editorial

Brute Force

Intuition

The most direct approach is to check every possible pair of elements. For each element, look at every element that comes after it and check if they add up to the target.

This approach completely ignores the fact that the array is sorted — it would work on an unsorted array too. Think of it like searching for a matching pair of socks by comparing every sock with every other sock. It works, but it is slow.

Step-by-Step Explanation

Let's trace through with numbers = [2, 3, 4], target = 6:

Step 1: Fix i = 0, value = 2. We need another element that, added to 2, equals 6.

Step 2: Try j = 1, value = 3. Sum = 2 + 3 = 5. Is 5 == 6? No, too small.

Step 3: Try j = 2, value = 4. Sum = 2 + 4 = 6. Is 6 == 6? YES! Found the pair.

Step 4: Return [1, 3] (converting 0-indexed [0, 2] to 1-indexed [1, 3]).

Brute Force — Checking All Pairs — Watch the nested loop check each pair of elements until it finds two that sum to the target.

Algorithm

  1. For each index i from 0 to n-2:
    • For each index j from i+1 to n-1:
      • If numbers[i] + numbers[j] == target, return [i+1, j+1]
  2. Return empty (should never reach here per constraints)

Code

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return {i + 1, j + 1};
                }
            }
        }
        return {};
    }
};
class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        n = len(numbers)
        for i in range(n):
            for j in range(i + 1, n):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]
        return []
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return new int[]{i + 1, j + 1};
                }
            }
        }
        return new int[]{};
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop iterates n times, and for each iteration the inner loop iterates up to n-1 times. Total pair comparisons: n×(n-1)/2, which is O(n²).

With n up to 3 × 10^4, this is up to ~4.5 × 10^8 operations — likely too slow.

Space Complexity: O(1)

Only a few integer variables are used. No additional data structures.

Why This Approach Is Not Efficient

The brute force checks all O(n²) pairs, which is far too slow for n up to 3 × 10^4. The fundamental problem is that for each element, we do a linear scan of the remaining array to find its complement — and we completely ignore that the array is sorted.

Key insight: Since the array is sorted, we can use binary search to find the complement in O(log n) instead of O(n). For each element numbers[i], the complement target - numbers[i] either exists in the remaining array or it doesn't, and binary search can determine this quickly. This reduces the total time from O(n²) to O(n log n).

Better Approach - Binary Search for Complement

Intuition

For each element numbers[i], we know exactly what value we need: complement = target - numbers[i]. In an unsorted array, finding this complement requires scanning all remaining elements (O(n)). But since the array is sorted, we can use binary search to find it in O(log n).

Think of looking up a word in a dictionary. You do not read every page — you jump to the approximate location and narrow down. That is binary search: each step halves the remaining search space.

We iterate through each element with a regular loop and, for each one, binary search the rest of the array for its complement. The first successful match gives us our answer.

Step-by-Step Explanation

Let's trace with numbers = [2, 7, 11, 15], target = 9:

Step 1: Start with i = 0, numbers[0] = 2. Complement = 9 - 2 = 7. Binary search for 7 in indices [1, 3].

Step 2: Binary search: lo = 1, hi = 3, mid = 2. numbers[2] = 11. Is 11 == 7? No. 11 > 7, so search the left half. Set hi = 1.

Step 3: Binary search: lo = 1, hi = 1, mid = 1. numbers[1] = 7. Is 7 == 7? YES! Found the complement at index 1.

Step 4: The pair is at indices 0 and 1 (0-indexed). Return [1, 2] (1-indexed).

Step 5: Verify: numbers[0] + numbers[1] = 2 + 7 = 9 = target ✓.

Binary Search for Complement — Halving the Search Space — For each element, we binary search the remaining sorted array for its complement. Each binary search step eliminates half the candidates.

Algorithm

  1. For each index i from 0 to n-2:
    • Compute complement = target - numbers[i]
    • Binary search for complement in the subarray numbers[i+1 .. n-1]:
      • lo = i + 1, hi = n - 1
      • While lo ≤ hi:
        • mid = lo + (hi - lo) / 2
        • If numbers[mid] == complement: return [i+1, mid+1]
        • If numbers[mid] < complement: lo = mid + 1
        • Else: hi = mid - 1
  2. Return empty (should never reach here)

Code

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        for (int i = 0; i < n; i++) {
            int complement = target - numbers[i];
            int lo = i + 1, hi = n - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (numbers[mid] == complement) {
                    return {i + 1, mid + 1};
                } else if (numbers[mid] < complement) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return {};
    }
};
class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        n = len(numbers)
        for i in range(n):
            complement = target - numbers[i]
            lo, hi = i + 1, n - 1
            while lo <= hi:
                mid = lo + (hi - lo) // 2
                if numbers[mid] == complement:
                    return [i + 1, mid + 1]
                elif numbers[mid] < complement:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return []
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        for (int i = 0; i < n; i++) {
            int complement = target - numbers[i];
            int lo = i + 1, hi = n - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (numbers[mid] == complement) {
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] < complement) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return new int[]{};
    }
}

Complexity Analysis

Time Complexity: O(n log n)

The outer loop runs n times. For each element, binary search runs in O(log n) time (halving the search space each step). Total: n × O(log n) = O(n log n).

With n = 3 × 10^4, this is roughly 3 × 10^4 × 15 ≈ 4.5 × 10^5 operations — comfortably fast.

Space Complexity: O(1)

Only a few integer variables (lo, hi, mid, complement) are used. No hash maps, no additional arrays.

Why This Approach Is Not Efficient

Binary search for each element gives O(n log n), which is fast enough to pass. But we are still not fully exploiting the sorted property.

Notice: when we fix numbers[i] and binary search for the complement, we treat each element independently. We discard information between iterations. If numbers[0] + numbers[3] > target, we know numbers[0] pairs with something to the LEFT of index 3 — and simultaneously, numbers[3] pairs with something to the LEFT of index 0 (impossible). This means numbers[3] is too big to pair with numbers[0].

Key insight: Place one pointer at the start (smallest) and one at the end (largest). Their sum tells us which direction to move:

  • Sum too large → decrease the right pointer (move to a smaller value)
  • Sum too small → increase the left pointer (move to a larger value)
  • Sum equals target → found!

Each step eliminates one candidate permanently, giving us O(n) total — the best possible for this problem.

Optimal Approach - Two Pointers

Intuition

Place a left pointer at the start of the array (smallest element) and a right pointer at the end (largest element). Compute their sum:

  • Sum == target: We found our pair.
  • Sum > target: The sum is too large. The only way to make it smaller is to decrease the larger element — move right one step leftward.
  • Sum < target: The sum is too small. The only way to make it bigger is to increase the smaller element — move left one step rightward.

Why does this work? Each pointer movement permanently eliminates one value from consideration. If numbers[left] + numbers[right] > target, then numbers[right] is too large to pair with numbers[left] (and with everything smaller than left too, since the array is sorted). So right can be safely discarded. Similarly for the left pointer.

Since we move exactly one pointer per step and the pointers converge toward each other, we make at most n-1 moves total. This gives O(n) time with O(1) space — the optimal solution.

Step-by-Step Explanation

Let's trace with numbers = [2, 7, 11, 15], target = 9:

Step 1: Initialize left = 0 (value 2), right = 3 (value 15).

Step 2: Compute sum = 2 + 15 = 17. Compare with target 9: 17 > 9. Sum is too large. Move right pointer left.

Step 3: Now left = 0 (value 2), right = 2 (value 11). Sum = 2 + 11 = 13. Compare: 13 > 9. Still too large. Move right pointer left.

Step 4: Now left = 0 (value 2), right = 1 (value 7). Sum = 2 + 7 = 9. Compare: 9 == 9. Match found!

Step 5: Return [1, 2] (1-indexed).

Notice: we found the answer in 3 sum computations. We never looked at elements unnecessarily — each step eliminated exactly one candidate.

Two Pointers — Converging from Both Ends — Watch two pointers start at opposite ends of the sorted array and converge toward each other. Each step eliminates one impossible candidate based on whether the sum is too large or too small.

Algorithm

  1. Initialize left = 0 and right = n - 1
  2. While left < right:
    • Compute sum = numbers[left] + numbers[right]
    • If sum == target: return [left + 1, right + 1]
    • If sum < target: left++ (need a bigger left value)
    • If sum > target: right-- (need a smaller right value)
  3. Return empty (should never reach here since a solution is guaranteed)

Code

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = (int)numbers.size() - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return {left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        return {};
    }
};
class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        left, right = 0, len(numbers) - 1

        while left < right:
            total = numbers[left] + numbers[right]
            if total == target:
                return [left + 1, right + 1]
            elif total < target:
                left += 1
            else:
                right -= 1

        return []
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        return new int[]{};
    }
}

Complexity Analysis

Time Complexity: O(n)

The left pointer only moves right, and the right pointer only moves left. In each iteration of the while loop, exactly one pointer moves. Since the two pointers start at distance n-1 apart and converge, the loop runs at most n-1 times. Each iteration does O(1) work (one addition, one comparison, one pointer move). Total: O(n).

With n = 3 × 10^4, this is at most ~3 × 10^4 operations — extremely fast.

Space Complexity: O(1)

Only two integer pointer variables (left and right) are used. No hash maps, no auxiliary arrays, no extra stack space. This satisfies the problem's explicit requirement for constant extra space.

Why this is optimal: Any algorithm must examine at least some elements to determine the answer. Two pointers examine at most n elements, each at most once. You cannot do better than O(n) for this problem since verifying a proposed answer already takes O(1), and the search space is linear.