Back to Two Pointers and Sliding Window
Two Sum II
Use two pointers starting at opposite ends of a sorted array. Converge inward based on whether the current sum is too small or too large — O(n) time, O(1) space.
Visualization
Speed
0
Comparisons
Searching
Status
2 + 40 = 42
Current Sum
0
2
L1
7
–2
11
–3
15
–4
18
–5
22
–6
30
–7
40
RLeft pointer (L)Right pointer (R)Found pairBetween pointers
Ready — press Play or step through.
Complexity
O(1)
Best Case
O(n)
Worst Case
O(n)
Average
O(1)
Space
How It Works
- 1Place left pointer at index 0, right pointer at index n-1
- 2Compute sum = arr[left] + arr[right]
- 3If sum == target: return [left+1, right+1]. If sum < target: left++. If sum > target: right--
- 4Repeat until left >= right (not found) or pair located
Why Sorted Order is Required
- •Sorted order gives a decision rule: sum too small means move left right; sum too large means move right left
- •Without sorting the same sum could be achieved by many pairs, so no single pointer move is safe
- •The problem name "Two Sum II" refers to LeetCode 167 where the input is guaranteed sorted
Active Recall Quiz
Question 1 of 3
Why does this two-pointer approach work on a sorted array but not on an unsorted one?