ASAPUtils
The signal
Sorted array + find a pair. That is the two-pointer signal in its canonical form, and the constraint “no O(n) extra space” removes the hash map so there is only one intended answer.
Approach ladder
1. Brute force — O(n²)
Every pair. Ignores the sortedness completely, which should feel wasteful — the problem went out of its way to tell you the input is sorted.
2. Binary search the complement — O(n log n)
For each a[i], binary search for target - a[i]. Uses the sortedness, O(1) space, and is a
genuinely respectable answer. Still beatable.
3. The insight
Start with the widest pair: l = 0, r = n-1. The sum tells you which direction to go:
- Sum too small → you need more.
a[r]is already the largest value available, soa[l]can never reach the target with anything. Discarda[l]:l++. - Sum too large → you need less.
a[l]is the smallest available, soa[r]is hopeless. Discard it:r--.
Each step eliminates an entire element from all future consideration. That’s the exchange argument, and it’s what you should say out loud rather than the code.
4. Optimal — O(n) time, O(1) space
vector<int> twoSum(vector<int>& a, int target) {
int l = 0, r = a.size() - 1;
while (l < r) {
int sum = a[l] + a[r];
if (sum == target) return {l + 1, r + 1}; // 1-indexed
if (sum < target) l++;
else r--;
}
return {};
}
function twoSum(a, target) {
let l = 0, r = a.length - 1;
while (l < r) {
const sum = a[l] + a[r];
if (sum === target) return [l + 1, r + 1]; // 1-indexed
if (sum < target) l++;
else r--;
}
return [];
}
Complexity
- Time O(n) — the pointers only move inward, so together they traverse the array once.
- Space O(1) — two indices.
Traps
- Returning 0-based indices. This problem is 1-indexed. Read the output spec twice; it’s the single most common wrong submission here.
while (l <= r). With<=an element can pair with itself.- Overflow in C++.
a[l] + a[r]on large values overflowsint; uselong longif the constraints allow big numbers.
Blank re-solve prompt
Given a sorted array and a target, return the 1-based indices of the two numbers that sum to it, in O(1) extra space. Then say, in one sentence, why moving the left pointer is safe.