#167 Two Sum II - Input Array Is Sorted
the problem
In plain words
Given a 1-indexed array sorted in non-decreasing order, return the indices (1-based) of the two numbers that add up to target. Exactly one solution exists; use O(1) extra space.
in numbers = [2,7,11,15], target = 9
out [1,2]
in numbers = [2,3,4], target = 6
out [1,3]
in numbers = [-1,0], target = -1
out [1,2]
- 2 ≤ n ≤ 3·10⁴
- Sorted non-decreasing
- Exactly one answer
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTwo pointers (opposite ends)
If the sum is too small, the left number is too small for every remaining partner — throw it away. Too big? Throw away the right number.
solutions
From brute force to optimal
Two nested loops over all pairs.
- For each i, for each j > i, test numbers[i] + numbers[j].
n(n−1)/2 pairs.
No extra structures.
class Solution { public int[] twoSum(int[] numbers, int target) { for (int i = 0; i < numbers.length; i++) { for (int j = i + 1; j < numbers.length; j++) { if (numbers[i] + numbers[j] == target) return new int[] {i + 1, j + 1}; } } return new int[] {-1, -1}; // problem guarantees one answer }}For each number, binary-search target − number in the part to its right.
- Loop i.
- Binary search for target − numbers[i] in [i+1, n−1].
n binary searches of log n each.
Indices only.
class Solution { public int[] twoSum(int[] numbers, int target) { for (int i = 0; i < numbers.length; i++) { int need = target - numbers[i]; int lo = i + 1, hi = numbers.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (numbers[mid] == need) return new int[] {i + 1, mid + 1}; if (numbers[mid] < need) lo = mid + 1; else hi = mid - 1; } } return new int[] {-1, -1}; }}Start at both ends; move left up if the sum is too small, right down if too big.
- left = 0, right = n−1.
- sum == target → answer.
- sum < target → left++.
- sum > target → right--.
Each step moves one pointer; at most n−1 steps.
Two indices.
class Solution { public int[] twoSum(int[] numbers, int target) { int left = 0, right = numbers.length - 1; while (left < right) { int sum = numbers[left] + numbers[right]; if (sum == target) return new int[] {left + 1, right + 1}; if (sum < target) left++; // need bigger → move left up else right--; // need smaller → move right down } return new int[] {-1, -1}; }}Dry run
in the room
How to say it in the interview
talk track
- Ask: 1-indexed output? Can values repeat? (Yes, e.g. [3,3] target 6.)
- Explain why discarding is safe — that's what the interviewer is really testing.
traps
- Returning 0-based indices — this problem wants
left + 1andright + 1. - Looping with
left <= right: the same element would be used twice. - Reaching for a HashMap: it works, but breaks the O(1)-extra-space rule.
what they ask next
Follow-ups
What if the array were not sorted?
That's LC 1 Two Sum: use a HashMap from value → index for O(n) time / O(n) space.
Count all pairs instead of returning one?
Same pointer moves; when sum == target handle runs of equal values carefully to count combinations.
before you submit
Edge cases to test
- Only two numbers: they must be the answer → [1, 2].
- Duplicates: [3, 3] with target 6 → [1, 2]; the pointers never pair an index with itself.
- Negative numbers: [-1, 0] with target -1 → [1, 2].
- The answer at the very start or the very end of 3·10⁴ numbers — the loop must not stop early.
practise next
Similar problems
- #1Two SumEasyin Hashing
- #153SumMediumin Two Pointers
- #163Sum ClosestMediumin Two Pointers