What it teaches: On sorted input, two pointers find a pair in O(n) time with O(1) space, beating the hash map's O(n) space.
Practise it on judges as “Two Sum II - Input Array Is Sorted”.
The problem
numbers is sorted in non-decreasing order. Find two numbers that add up to target and return their 1-based indexes [index1, index2] with index1 < index2. Exactly one solution exists. Use only O(1) extra space.
These clues point to Two Pointers: Opposite Ends: Start one pointer at each end and move them towards each other, using a rule to decide which one moves.
Stuck? Take one hint at a time
Solution.java · starter
class Solution {
public int[] twoSum(int[] numbers, int target) {
int L = 0, R = numbers.length - 1;
return new int[0];
}
}
Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
L = 0, R = n − 1. If the sum is below target, L++; above, R--; equal, return [L + 1, R + 1].
▶ Dry run: Closing in on 9numbers = [2, 7, 11, 15], target = 9
2
0
↑L
7
1
11
2
15
3
↑R
Step 1/32 + 15 = 17 > 9: drop 15.
Approach 1
class Solution {
public int[] twoSum(int[] numbers, int target) {
int L = 0, R = numbers.length - 1;
while (L < R) {
int sum = numbers[L] + numbers[R];
if (sum == target) return new int[]{L + 1, R + 1};
if (sum < target) L++;
else R--;
}
return new int[0];
}
}
Verdict: Uses the sorted order; no extra memory.
Before you submit
Edge cases and common mistakes
Test these inputs
Negative numbers
Duplicates (e.g. [1, 1, 3], target 2)
Answer is the first and last element
Mistakes people make
Returning 0-based indexes.
Using a HashMap (works, but breaks the O(1) space rule).