Two Sum II - Input Array Is Sorted
Understanding the Problem
We have a sorted array and need to find two numbers that add up to a given target. Three constraints shape the approach: the array is sorted, we must return 1-indexed positions, and we can only use constant extra space.
The constant-space requirement is what separates this problem from the original Two Sum. It rules out the hash map approach, which would store seen values as it scans. We have to find the pair using the structure of the array itself instead of an auxiliary data structure.
The sorted order gives us that structure. Because the array is sorted, the position of an element tells us how its value compares to everything around it, and we can use that to decide where the matching pair must lie.
Key Constraints:
numbers.lengthup to3 * 10^4→ an O(n^2) brute force runs about 4.5 * 10^8 pair checks in the worst case, slow enough that we should aim for O(n log n) or O(n).- The array is sorted → ordering enables binary search and the two-pointer technique, neither of which works on an unsorted array.
- Constant extra space required → a hash map is off-limits, even though it would pass on LeetCode.
- Exactly one solution exists → no need to handle a "no solution" case.
Approach 1: Brute Force
Intuition
Try every pair of elements and check if it adds up to the target. For each element at index i, check every element at index j > i. If their sum equals the target, return the 1-indexed positions.
This ignores the sorted property entirely, so it leaves a lot of performance on the table. It works as a correctness baseline before we optimize.
Algorithm
- Loop through each index
ifrom 0 to n-2. - For each
i, loop through each indexjfrom i+1 to n-1. - If
numbers[i] + numbers[j]equals the target, return[i+1, j+1]. - Since a solution is guaranteed, we'll always find it before exhausting all pairs.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each of the n elements, we potentially scan through all remaining elements. In the worst case, the answer is at the very end, so we check roughly n*(n-1)/2 pairs.
- Space Complexity: O(1). We only use a few variables for loop indices. No additional data structures.
The brute force scans linearly for each element's complement. Because the array is sorted, the next approach replaces that linear scan with a binary search.
Approach 2: Binary Search
Intuition
Fix one element and search for its complement. For each numbers[i], the value we need is complement = target - numbers[i]. Since the array is sorted, a binary search on the portion after index i finds that complement in O(log n) instead of the O(n) linear scan.
We search only the subarray to the right of i (indices i+1 onward). This avoids pairing an element with itself and avoids re-checking pairs we already tested when i was smaller.
Algorithm
- For each index
ifrom 0 to n-2: - Compute the complement:
complement = target - numbers[i]. - Binary search for
complementin the subarray from indexi+1ton-1. - If found at index
j, return[i+1, j+1].
Example Walkthrough
Code
- Time Complexity: O(n log n). We iterate through n elements, and for each one we run a binary search on the remaining elements, which takes O(log n).
- Space Complexity: O(1). Only a few variables for pointers and the complement. No extra data structures.
Binary search cut the inner loop from O(n) to O(log n), but each element is still searched independently, repeating work. The next approach scans the array once with two pointers that move toward each other, reaching O(n).
Approach 3: Two Pointers (Optimal)
Intuition
Place one pointer at the beginning (smallest element) and one at the end (largest element). Their sum tells us which way to move.
- If the sum is less than the target, the only way to increase it is to use a larger value, so move the left pointer right.
- If the sum is greater than the target, the only way to decrease it is to use a smaller value, so move the right pointer left.
- If the sum equals the target, we found the pair.
Each move discards one element, and because the array is sorted, the discarded element can never be part of the answer with any remaining element. The window between the two pointers shrinks by one each step, so the scan ends in a single pass.
The reason a discarded element is safe to drop: suppose numbers[left] + numbers[right] < target. Every element from left+1 to right is at most numbers[right] (the array is sorted), so pairing numbers[left] with any of them gives a sum at most numbers[left] + numbers[right], which is still below the target. No pair involving numbers[left] can reach the target, so removing left loses no valid answer. The symmetric argument holds when the sum exceeds the target and we drop right. Since exactly one solution exists, the pointers cannot pass it, and they meet at it before crossing.
Algorithm
- Initialize
left = 0andright = n - 1. - While
left < right: - Compute
sum = numbers[left] + numbers[right]. - If
sum == target, return[left + 1, right + 1]. - If
sum < target, incrementleft(we need a larger sum). - If
sum > target, decrementright(we need a smaller sum). - Return the result (guaranteed to be found in the loop).
Example Walkthrough
Code
- Time Complexity: O(n). Each iteration moves either the left pointer right or the right pointer left. The two pointers start n-1 positions apart and converge, so at most n-1 iterations.
- Space Complexity: O(1). We only use two pointer variables. No extra data structures.