Two Sum II - Input Array Is Sorted

LeetCode 167: Two Sum II - Input Array Is Sorted Solution & Explanation

Problem Overview

TL;DR: Use two pointers starting at the beginning and end of the sorted array to find the target sum in linear time and constant space.

The LeetCode 167 problem, "Two Sum II - Input Array Is Sorted," asks us to identify the indices of two numbers within a sorted array that add up to a specific target value. Unlike the standard Two Sum problem, the input array is guaranteed to be sorted in non-decreasing order, and we are restricted to using constant extra space. The result must be returned as a 1-indexed array.

This is a classic interview question that tests the ability to leverage data properties (sorting) to optimize space complexity compared to the hash map approach used in the unsorted variation.

Brute Force Approach for Two Sum II - Input Array Is Sorted

The naive approach involves checking every possible pair of numbers in the array to see if their sum equals the target. This is done using nested loops.

Pseudo-code:

For i from 0 to length - 2:
    For j from i + 1 to length - 1:
        If numbers[i] + numbers[j] == target:
            Return [i + 1, j + 1]

Complexity Analysis:

• Time Complexity: $O(N^2)$, where $N$ is the number of elements. We iterate through the array twice.
• Space Complexity: $O(1)$.

Why it fails: While this solution is correct, it is inefficient. The constraint allows up to $3 \times 10^4$ elements. An $O(N^2)$ solution results in approximately $9 \times 10^8$ operations, which will likely result in a Time Limit Exceeded error. Furthermore, this approach completely ignores the fact that the input array is sorted, missing a critical optimization opportunity.

Algorithm Strategy: Two Pointer Patterns

1. Initialization: Initialize two pointers: left pointing to the start of the array (index 0) and right pointing to the end of the array (index length - 1).
2. Iterative Search: Enter a loop that continues as long as left < right.
3. Summation: In each iteration, calculate current_sum = numbers[left] + numbers[right].
4. Comparison and Movement:
   • If current_sum equals target, we have found the solution. Return [left + 1, right + 1] (adjusting for 1-based indexing).
   • If current_sum is greater than target, decrement the right pointer to reduce the sum.
   • If current_sum is less than target, increment the left pointer to increase the sum.
5. Termination: Since the problem guarantees exactly one solution, the loop will always return inside the equality check.

Execution Flow

Let's trace the logic with numbers = [2, 7, 11, 15] and target = 9.

1. Start: left points to 2 (index 0), right points to 15 (index 3).
2. Iteration 1:
   • current_sum = 2 + 15 = 17.
   • 17 > 9 (target). The sum is too large.
   • Move right pointer to the left (index 2).
3. Iteration 2:
   • left points to 2 (index 0), right points to 11 (index 2).
   • current_sum = 2 + 11 = 13.
   • 13 > 9. The sum is still too large.
   • Move right pointer to the left (index 1).
4. Iteration 3:
   • left points to 2 (index 0), right points to 7 (index 1).
   • current_sum = 2 + 7 = 9.
   • 9 == 9. Target found.
5. Return: Indices [0 + 1, 1 + 1] which is [1, 2].

Proof of Correctness

The correctness relies on the invariant that the solution pair MUST lie between the left and right pointers.

Suppose the correct solution is at indices (i, j) where i < j.

• Our pointers start at 0 and n-1. Thus left <= i and right >= j.
• Suppose we are at a state where left is correct (left == i), but right is still to the right of the solution (right > j).
• Because the array is sorted, numbers[right] is greater than numbers[j].
• Therefore, numbers[left] + numbers[right] > numbers[i] + numbers[j] (which is target).
• The algorithm correctly decides to decrement right. It will never increment left (moving past the correct i) because the sum is strictly greater than the target.
• The same logic applies symmetrically if right is correct but left is too small.
• We only eliminate indices that logically cannot be part of the solution.

Pattern Reuse Notes

The Two Pointers - Converging pattern is a fundamental technique for sorted arrays or problems involving "containers" where width is a factor.

• LeetCode 11: Container With Most Water: Uses converging pointers to maximize area. The decision to move pointers is based on the height of the lines (move the shorter line).
• LeetCode 15: 3Sum: Reduces the 3-sum problem to the 2-sum problem. We iterate one number and use the converging pointers pattern to find the other two.
• LeetCode 16: 3Sum Closest: Similar to 3Sum, but instead of looking for exact equality, we track the minimum difference using converging pointers.
• LeetCode 18: 4Sum: An extension of 3Sum, adding another layer of loops before applying the converging pointers strategy.

Reference Implementation

C++ Solution for LeetCode 167

1class Solution {
2public:
3    vector<int> twoSum(vector<int>& numbers, int target) {
4        int left = 0;
5        int right = numbers.size() - 1;
6        
7        while (left < right) {
8            int current_sum = numbers[left] + numbers[right];
9            
10            if (current_sum == target) {
11                // Return 1-based indices
12                return {left + 1, right + 1};
13            } else if (current_sum > target) {
14                // Sum is too large, decrease it by moving right pointer
15                right--;
16            } else {
17                // Sum is too small, increase it by moving left pointer
18                left++;
19            }
20        }
21        
22        return {}; // Should not be reached per problem constraints
23    }
24};

Java Solution for LeetCode 167

1class Solution {
2    public int[] twoSum(int[] numbers, int target) {
3        int left = 0;
4        int right = numbers.length - 1;
5        
6        while (left < right) {
7            int currentSum = numbers[left] + numbers[right];
8            
9            if (currentSum == target) {
10                // Return 1-based indices
11                return new int[] { left + 1, right + 1 };
12            } else if (currentSum > target) {
13                // Sum is too large, need smaller number
14                right--;
15            } else {
16                // Sum is too small, need larger number
17                left++;
18            }
19        }
20        
21        return new int[] {}; // Should not be reached
22    }
23}

Python Solution for LeetCode 167

1class Solution:
2    def twoSum(self, numbers: List[int], target: int) -> List[int]:
3        left = 0
4        right = len(numbers) - 1
5        
6        while left < right:
7            current_sum = numbers[left] + numbers[right]
8            
9            if current_sum == target:
10                # Return 1-based indices
11                return [left + 1, right + 1]
12            elif current_sum > target:
13                # Sum is too large, move right pointer to the left
14                right -= 1
15            else:
16                # Sum is too small, move left pointer to the right
17                left += 1
18                
19        return []