Two Sum II
Medium · Arrays & Hashing · Array · Two Pointers · Binary Search
Problem
You are given a 1-indexed array of integers numbers sorted in non-decreasing order, and an integer target. Exactly one pair of distinct positions sums to target.
Return the positions [index1, index2] of those two numbers, 1-indexed, with index1 < index2. You may not use the same element twice.
Your solution should use only constant extra space.
Examples
Input: numbers = [1,4,6,9,12], target = 15 Output: [3,4]
6 + 9 = 15, at 1-indexed positions 3 and 4.
Input: numbers = [-5,-2,0], target = -7 Output: [1,2]
-5 + -2 = -7, at positions 1 and 2.
Input: numbers = [3,3], target = 6 Output: [1,2]
The two 3s are different elements, so they may pair.
Constraints
- 2 <= len(numbers) <= 3 · 10^4
- -1000 <= numbers[i] <= 1000
- numbers is sorted in non-decreasing order
- -1000 <= target <= 1000
- Exactly one pair of positions sums to target
Approaches
- Binary search for each complement — time O(n log n), space O(1)
Follow-up
Why is no pair ever skipped? When numbers[lo] + numbers[hi] < target, the left element is too small even with the largest partner left, so it can be dropped; symmetrically for a sum that is too large. The answer pair is never dropped because, until it is found, one of its two ends is always strictly inside the window. The use cases count all pairs at most the target and find the closest pair sum.
Related problems
Start free on Cariara · Coding problems · System design studio
