DSA Tracker

Visualize

Converging Pointers

Opposite-ends two pointers

time O(n)space O(1)

Two pointers start at opposite ends of a sorted array and walk toward each other, using the sort order to safely discard one candidate every step. Reach for it whenever sorted data lets a single comparison tell you which end to shrink.

Details

Animated on: Two Sum II: find two numbers in the sorted array [1, 3, 4, 6, 8, 11] that add up to 10

Problem:Two Sum II - Input Array Is SortedMedium

Pattern:Two Pointers

Opposite-ends two pointers

step 1 / 11

1
[0]
3
[1]
4
[2]
6
[3]
8
[4]
11
[5]

Sorted array, target 10. Put l on the smallest value and r on the largest — the sum can only be steered from these two ends.

  • l=0· arr[0] = 1
  • r=5· arr[5] = 11
Pseudocode
1FUNCTION twoSumSorted(arr, target):
2  set l to 0 and r to the last index of arr
3  WHILE l < r:
4    sum = arr[l] + arr[r]
5    IF sum equals target: RETURN [l, r]
6    IF sum < target: move l one step right
7    ELSE: move r one step left
8  END WHILE
9  RETURN nothing (no pair found)
10END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. Sorted array, target 10. Put l on the smallest value and r on the largest — the sum can only be steered from these two ends.
  2. sum = arr[l] + arr[r] = 1 + 11 = 12. Compare it against target 10.
  3. 12 > 10: too big. Even the smallest value 1 overshoots with 11, so 11 can pair with nothing. Discard it — r moves left.
  4. New pair: sum = 1 + 8 = 9. Compare against 10.
  5. 9 < 10: too small. 8 is the biggest partner left, so 1 can never reach 10 with anyone. Discard 1 — l moves right.
  6. sum = 3 + 8 = 11. Compare against 10.
  7. 11 > 10: overshoot. 8 just failed with the smallest remaining value 3, so any partner for 8 overshoots too. Discard 8 — r moves left.
  8. sum = 3 + 6 = 9. Compare against 10.
  9. 9 < 10: too small. 6 is the largest partner left for 3 and it still falls short — 3 is out. l moves right.
  10. sum = 4 + 6 = 10. Compare against 10.
  11. 10 === target. Found it: arr[2]=4 + arr[3]=6 = 10. Return [2, 3] — one pass, each element examined at most once.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Two Sum II - Input Array Is Sorted in the editorAll Two Pointers problemsBack to roadmap