RoadmapDay 12 / 80
DSAMonth 1 · Week 3

Day 12: Two Pointers Technique

Recognize sorted-array and palindrome-style problems that collapse from O(n²) to O(n) with two pointers moving toward or away from each other.

Mark this day complete

Study

Concepts

Converging pointers on sorted data

When an array is sorted and you need a pair/triplet satisfying a condition, place one pointer at each end and move them based on comparing the current sum/difference to the target — moving `left` up increases the sum, moving `right` down decreases it. Each step eliminates one element permanently, giving O(n) instead of the O(n²) nested-loop scan.

This only works because the array is sorted — sortedness is what lets you infer "the sum is too big, so decreasing right definitely helps" without re-checking every pair.

Same-direction pointers for in-place partitioning

A second flavor uses both pointers moving in the same direction at different speeds — a "slow" write pointer and a "fast" read pointer — to compact/filter an array in place (e.g. removing duplicates from a sorted array, or moving all zeros to the end) in O(n) time and O(1) extra space.

See It

Visualizations

Visualization

Two Sum II (sorted array) — pointers converge

target = 9. left+right too big → move right left; too small → move left right.

0
1
2
3
4
1
2
4
7
11

Build It

Code Examples

Two Sum II on a sorted array — converging pointers

js
function twoSumSorted(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;   // need a bigger sum
    else right--;                // need a smaller sum
  }
  return [];
}

console.log(twoSumSorted([1, 2, 4, 7, 11], 9)); // [1, 3] -> values 2 + 7

Remove duplicates from a sorted array in place — same-direction pointers

js
function removeDuplicates(nums) {
  if (nums.length === 0) return 0;
  let slow = 0; // last position of a confirmed-unique element

  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {
      slow++;
      nums[slow] = nums[fast];
    }
  }
  return slow + 1; // new length of the unique prefix
}

const arr = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
const len = removeDuplicates(arr);
console.log(len, arr.slice(0, len)); // 5 [0, 1, 2, 3, 4]

Remember

Key Takeaways

  • Converging two pointers requires sorted input — that sortedness is what justifies each pointer move.
  • Each comparison eliminates exactly one element from further consideration — that is the O(n) guarantee.
  • Same-direction (slow/fast) pointers are the standard way to filter/compact an array in O(1) extra space.
  • If the array is NOT sorted, either sort it first (O(n log n)) or switch to the hash-map pattern from Day 11.
  • Always state the invariant out loud: "everything left of slow is confirmed unique" — interviewers grade on this.

Do It

Practice

  1. 1Solve "3Sum" by fixing one index in a loop and running the two-pointer technique on the remaining sorted sub-array.
  2. 2Solve "Container With Most Water" with converging pointers, and explain why moving the shorter wall is always the correct move.
  3. 3Solve "Move Zeroes" in place using the same-direction slow/fast pattern from the duplicates example.