AlgoViz
HomeTwo Pointers

Introduction

Easy

Why two indices beat one nested loop

In simple words

Instead of checking every pair, use two fingers that move through the list smartly, so you pass through only once.

The idea

Instead of checking every pair with two nested loops (O(n²)), keep two indices that move toward each other or at different speeds. Each element is visited a constant number of times, so the whole scan is O(n).

The trick

  • Works when the array is sorted, or when order lets you rule out whole ranges at once.
  • Moving a pointer is a decision: 'this element can never be part of a better answer.'
L
R
2
4
7
11
15
0
1
2
3
4

Step 1 of 4. We want two numbers that add up to 9. Put one finger on the smallest, one on the biggest. Values: 2, 4, 7, 11, 15. Pointers: L at index 0, R at index 4.

1/4
Optimal
timeO(n)spaceO(1)

One pass, two cursors, constant extra memory.

1// two indices, moving inward on a sorted array2let l = 0, r = nums.length - 1;3while (l < r) {4  const sum = nums[l] + nums[r];5  if (sum === target) return [l, r];6  if (sum < target) l++;   // need a bigger sum7  else r--;                // need a smaller sum8}

Input

array
[2, 4, 7, 11, 15]

Memory

L
= 0 [2]
R
= 4 [15]
sum
—
target
—

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
sorted = [1, 3, 4, 6], target = 7
Output:
(3, 4)
Explanation:
Start at both ends: 1+6 = 7 is too small only if the target were larger; here 1+6 = 7 hits. Because the array is sorted, one comparison rules out a whole side.

Example 2

Input:
[1, 3, 4, 6] with a nested loop
Output:
same answer, 6 pairs tested
Explanation:
Two pointers test 4 positions instead of 6, and the gap widens to n versus n² as the array grows.

Finished the walkthrough? Add it to your streak.