Fast/slow pointers for linked lists, left/right squeeze for sorted arrays, and partition-based techniques -- one pattern, many problems

Two Pointers

Two pointers is deceptively simple: instead of one index scanning through data, you use two. The magic is in how they move relative to each other. This single idea solves dozens of problems that would otherwise require nested loops.

There are three main variants:

Fast/slow pointers -- both start at the same place, one moves faster
Left/right squeeze -- start at opposite ends, move inward
Partition-based -- rearrange elements in-place around a condition

Fast/Slow Pointers

The classic use case: detecting cycles in a linked list. One pointer moves one step at a time, the other moves two. If there is a cycle, the fast pointer will eventually lap the slow pointer.

interface ListNode {
  val: number;
  next: ListNode | null;
}

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;

    if (slow === fast) return true;
  }

  return false;
}

Time: O(n), Space: O(1). Without this trick, you would need a hash set to track visited nodes, costing O(n) space.

Finding the Cycle Start

Once the fast and slow pointers meet, reset one to the head. Move both one step at a time -- they will meet at the cycle entrance. This is Floyd's algorithm.

function detectCycleStart(head: ListNode | null): ListNode | null {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;

    if (slow === fast) {
      // Reset slow to head, advance both by 1
      slow = head;
      while (slow !== fast) {
        slow = slow!.next;
        fast = fast!.next;
      }
      return slow;
    }
  }

  return null;
}

Middle of Linked List

When the fast pointer reaches the end, the slow pointer is at the middle.

function findMiddle(head: ListNode | null): ListNode | null {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
  }

  return slow;
}

Left/Right Squeeze

Start two pointers at opposite ends of a sorted (or partially structured) array, and move them inward based on a condition. This eliminates the need for nested loops.

Container With Most Water

Given heights, find two lines that together with the x-axis form a container holding the most water.

function maxArea(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let maxWater = 0;

  while (left < right) {
    const width = right - left;
    const h = Math.min(height[left], height[right]);
    maxWater = Math.max(maxWater, width * h);

    // Move the shorter side inward -- moving the taller side
    // can never increase the area
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return maxWater;
}

Time: O(n), Space: O(1). Brute force would be O(n^2).

3Sum

Find all unique triplets that sum to zero. Sort first, then fix one element and use left/right squeeze on the rest.

function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  const result: number[][] = [];

  for (let i = 0; i < nums.length - 2; i++) {
    // Skip duplicates for the first element
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    let left = i + 1;
    let right = nums.length - 1;

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        // Skip duplicates
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }

  return result;
}

Time: O(n^2), Space: O(1) (excluding output). The sort is O(n log n), dominated by the O(n^2) two-pointer scan.

Partition-Based Two Pointers

Use two pointers to partition an array in-place. One pointer tracks the "write" position, the other scans.

Remove Duplicates from Sorted Array

function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;

  let write = 1; // slow pointer: next write position

  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[read - 1]) {
      nums[write] = nums[read];
      write++;
    }
  }

  return write;
}

Dutch National Flag (3-Way Partition)

Sort an array of 0s, 1s, and 2s in one pass using three pointers.

function sortColors(nums: number[]): void {
  let low = 0;          // boundary for 0s
  let mid = 0;          // current element
  let high = nums.length - 1; // boundary for 2s

  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
      // Don't advance mid -- the swapped element needs checking
    }
  }
}

The Two-Pointer Template

Most two-pointer problems fit one of these templates:

// Template 1: Left/Right Squeeze
function leftRightSqueeze(arr: number[]): void {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    // Process arr[left] and arr[right]
    if (/* move left condition */) {
      left++;
    } else {
      right--;
    }
  }
}

// Template 2: Fast/Slow (same direction)
function fastSlow(arr: number[]): void {
  let slow = 0;

  for (let fast = 0; fast < arr.length; fast++) {
    if (/* condition to write */) {
      arr[slow] = arr[fast];
      slow++;
    }
  }
}

When to Use Two Pointers

The input is sorted or has some ordering property
You need to find pairs or triplets satisfying a condition
You need to do something in-place with O(1) space
You are working with a linked list and need cycle detection or middle finding
The brute force involves nested loops over the same array

Complexity Summary

Problem	Time	Space
Linked list cycle	O(n)	O(1)
Container with most water	O(n)	O(1)
3Sum	O(n^2)	O(1)
Remove duplicates	O(n)	O(1)
Dutch national flag	O(n)	O(1)

The recurring theme: two pointers almost always give you O(1) space and reduce an O(n^2) brute force to O(n) or keep it at the optimal complexity for the problem.

Two Pointers

On this page