-
Notifications
You must be signed in to change notification settings - Fork 0
041 — Two Sum II Input Array Is Sorted
LeetCode 167 · Medium. Given a 1-indexed, already-sorted array numbers in non-decreasing order, return the 1-indexed indices of the two numbers that add up to target. You must use only constant extra space.
Picture a balance scale with a row of weights laid out in front of you, sorted from lightest to heaviest. You want to find two weights that, placed together on the scale, hit an exact target reading. Start by putting the lightest weight and the heaviest weight on together. If the total is too light, swapping in a heavier item can only help — but which one? Since everything's sorted, the safest and most informative swap is to trade the lightest weight for the next-lightest one, nudging the total up by the smallest possible amount. If the total is too heavy, you do the mirror move: trade the heaviest weight for the next-heaviest-down, nudging the total down. Because the row is sorted, every swap moves the total in a direction you can predict — no guessing, no re-checking pairs you've already ruled out.
"Sorted array" + "return the indices of two numbers that add up to a target" is one of the clearest tells for Two Pointers over a hash map. Compare this to plain Two Sum: there, the array was unsorted and a hash map's O(1) complement lookup was the only way to get O(n) time. Here, sortedness itself gives you the monotonic property Two Pointers needs — moving the left pointer can only increase the sum, moving the right pointer can only decrease it — so converging pointers reach the answer in O(n) time and, crucially, O(1) space, which the problem explicitly asks for.
Check every pair of indices and see if their values sum to the target, returning 1-indexed positions.
func twoSumBruteForce(_ numbers: [Int], _ target: Int) -> [Int] {
for i in 0..<numbers.count {
for j in (i + 1)..<numbers.count {
if numbers[i] + numbers[j] == target {
return [i + 1, j + 1] // problem is 1-indexed
}
}
}
return [] // problem guarantees exactly one solution
}Big-O: O(n²) time from the nested loop — and notice it doesn't even use the fact that the array is sorted. O(1) extra space.
Start one pointer at the first (smallest) element and one at the last (largest). At each step, compare the sum against the target: too small means move left inward to increase the sum, too big means move right inward to decrease it.
func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
var left = 0
var right = numbers.count - 1
while left < right {
let sum = numbers[left] + numbers[right]
if sum == target {
return [left + 1, right + 1] // problem is 1-indexed
} else if sum < target {
left += 1
} else {
right -= 1
}
}
return [] // problem guarantees exactly one solution
}Big-O: O(n) time — the two pointers together cover the array once, closing the gap between them by at least one index per step. O(1) extra space — exactly what the problem requires.
The brute force treats "sorted" as irrelevant trivia and re-checks every pair anyway. But sortedness is exactly the property that makes a pointer's movement decisive: if numbers[left] + numbers[right] is too small, then pairing numbers[left] with anything to the left of right would be even smaller (since the array only grows as you move right) — so every one of those pairs can be safely discarded in one comparison, and the only sensible move is to grow the left side. The same logic runs in reverse for a too-big sum. That single monotonic guarantee is what collapses O(n²) pair-checking into a single O(n) sweep with two pointers instead of a hash map — the space savings matter because the problem forbids extra data structures.
- Two Pointers — the converging-pointer template this solution instantiates directly.
- Arrays & Strings — the sorted array being scanned.
- Two Sum — the unsorted, hash-map-based sibling of this exact same "pair sums to target" question.
Two Sum II is a balance scale loaded with sorted weights — swap the light side up or the heavy side down until the reading lands exactly on target.
Why does the two-pointer approach require the array to be sorted, while the hash-map approach from Two Sum works on an unsorted array with no extra guarantee at all? Concretely: if you ran this exact two-pointer algorithm on an unsorted array, what specific step in the reasoning above would break?