Two pointers: two indexes doing the work of a nested loop

Keep two indexes into the array and move them by a rule, so that together they pass over the array once. There are two shapes. Either they start at both ends and walk inward. Or they both walk forward, with one reading and one writing.

Think of it like this: two people folding a long tablecloth. They start at opposite ends and walk toward each other, meeting in the middle. Neither one ever walks back, so the whole cloth is handled in one pass.

What a pointer is

Shape 1: opposite ends, moving inward

Shape 2: same direction, read and write

How to spot it

Words and constraints in a problem that point to this pattern:

• “The array is sorted” together with “find a pair / triple that…”
• “In place”, “without extra space”, “O(1) extra memory”
• “Reads the same forwards and backwards”, or comparing the start with the end
• “Remove / move / keep only…” while preserving order
• Two sorted lists that need to be walked together

Watch it work

The template

// Shape 1: opposite ends, moving inward (usually needs sorted input)
function oppositeEnds(nums: number[]): void {
  let left = 0;                       // first index
  let right = nums.length - 1;        // last index
  while (left < right) {              // use <= if the middle element needs handling too
    const a = nums[left];
    const b = nums[right];
    if (/* left end is done with */ a < b) {
      left++;                         // never moves back, so at most n moves
    } else {
      right--;                        // never moves back either
    }
  }
}

// Shape 2: same direction, read and write (filter in place)
function readWrite(nums: number[]): number {
  let write = 0;                      // next slot for a value we keep
  for (let read = 0; read < nums.length; read++) {
    if (/* keep nums[read]? */ nums[read] !== 0) {
      nums[write] = nums[read];       // copy the keeper forward
      write++;                        // the kept part grows by one
    }
  }
  return write;                       // nums[0 .. write-1] is the result
}

Worked example

1. The first idea: walk the array. Whenever you see a 0, remove it with splice and push a 0 on the end. Careful: after a splice, the next element slides into index i, so you must not move i forward. It works. But each splice shifts every later element one place left. That's O(n) per zero, so O(n²) when there are many zeros.

   let i = 0;
   let checked = 0;
   while (checked < nums.length) {
     if (nums[i] === 0) {
       nums.splice(i, 1);
       nums.push(0);
     } else {
       i++;
     }
     checked++;
   }
   

2. Spot the waste. The non-zero numbers keep getting shifted left by one, over and over. Each one only needs to move once, straight to its final spot.

3. Use read/write. read visits every element. write is where the next non-zero belongs. When read finds a non-zero, copy it to write and move write forward. After the loop, the first write slots hold the non-zeros in order. Fill the rest with zeros.

   function moveZeros(nums: number[]): void {
     let write = 0;
     for (let read = 0; read < nums.length; read++) {
       if (nums[read] !== 0) {
         nums[write] = nums[read];
         write++;
       }
     }
     for (let i = write; i < nums.length; i++) {
       nums[i] = 0;
     }
   }
   

4. Trace it on [0, 1, 0, 3, 12]. read 0: zero, skip. read 1: copy 1 to index 0, write = 1. read 2: skip. read 3: copy 3 to index 1, write = 2. read 4: copy 12 to index 2, write = 3. Fill indexes 3 and 4 with 0: [1, 3, 12, 0, 0]. Correct.

5. Edge cases. [0, 0]: no copies, write stays 0, both slots filled with 0. [4, 5]: every element copies onto itself, nothing is filled. []: neither loop runs. Two passes over the array: O(n) time, O(1) extra space.

Common mistakes

• Using opposite-ends on an unsorted array. Moving a pointer throws away values that could still be part of the answer, so it misses pairs.
• Mixing up while (left <= right) and while (left < right). The wrong one either skips the middle element or uses the same element twice as a "pair".
• Moving the wrong pointer, or both at once when only one should move. The loop skips over the answer.
• In read/write, moving write on every step instead of only when you keep a value. The result then includes the values you meant to drop.
• Returning the array when the problem wants the new length, or the other way round. Read what the prompt asks for.

Cost

In interviews