Module F-8·16 min read

Converging and fast/slow pointer patterns that turn O(n²) nested loops into O(n) passes.

JJS

Written by Jatin Jain Saraf · Senior Software Engineer

Module F-8 — Two-Pointer Technique

Q: In `twoSumSorted`, why is it always safe to move the `left` pointer forward when the current sum is smaller than the target, without ever needing to check smaller values of `right` first?

Because the array is sorted, decreasing `right` can only decrease or keep the sum the same, never increase it — so if the sum is too small, the only pointer move that could possibly reach the target is increasing `left` to a larger value. — Because the array is sorted in ascending order, every value to the left of the current `right` is less than or equal to `nums[right]` — so decreasing `right` can never increase the sum. If the current sum is already too small, decreasing `right` further only makes it smaller or keeps it the same, guaranteeing it can never reach the target from below. The only remaining option that could possibly increase the sum is moving `left` to a larger value. Option B is false — the two pointers move independently based on the sum comparison, not in lockstep. Option C ignores the entire justification the module gives — sortedness is precisely what licenses this decision; without it, the two-pointer approach would not be valid. Option D fabricates a per-iteration re-sort that does not appear anywhere in the function and would defeat the point of the O(n) approach.

Q: In `maxArea` (Container With Most Water), why is it always safe to discard the shorter of the two current lines and move its pointer inward, rather than the taller one?

The trapped water's height is capped by the shorter of the two lines regardless of how tall the other one is, so keeping the shorter line while shrinking the width can never produce a better result than what's already been measured — discarding it and trying the next candidate is the only move that could possibly improve on the current best. — The area between any two lines is `width × min(height_left, height_right)` — the shorter line is always the limiting factor. Any other line paired with that same shorter line would produce, at best, the same height and a width no larger than what's already been measured (since moving inward only shrinks width). That makes every remaining pairing that still includes the shorter line strictly no better than what's already recorded, so it's always safe to move past it and look for a taller replacement. Option B is a fabricated and meaningless claim — there's no such thing as a "structurally invalid" line. Option C is incorrect — the module's whole point is that moving the shorter side is deliberate and load-bearing for correctness, not an arbitrary tie-break; moving the taller side instead could skip over the actual best answer. Option D ignores the entire premise — height comparison is exactly what determines which pointer to move.

Q: According to the module, what specific property must generally hold for a two-pointer approach to correctly replace a nested-loop, all-pairs comparison?

The data must have some exploitable structure — such as sortedness, or a known relationship between traversal speeds — that allows a single comparison to safely rule out an entire range of remaining possibilities, rather than needing to check them individually. — The module explicitly identifies "some exploitable structure" — sortedness in the converging-pointer examples, or a known speed relationship in the fast/slow examples — as the property that lets a two-pointer approach discard whole ranges of possibilities per comparison, which is what makes it faster than checking every pair individually. Without such structure, there's no basis for deciding which pointer to safely move. Option A invents an arbitrary and incorrect size restriction never mentioned in the module. Option C overstates the technique's applicability — the module is explicit that the pattern "works specifically when" exploitable structure exists, not universally. Option D is contradicted directly by the module itself, which applies the technique to strings (Module F-3's palindrome check) and previews its use on linked lists (Module P-2) — it is not limited to numeric arrays.

What this module covers: Two pointers walking through the same data — either converging toward each other or moving at different speeds — turn a surprising number of O(n²) problems into O(n). You've already seen fragments of this pattern: array reversal and palindrome checking in Modules F-2 and F-3, and the head/tail pointers behind an efficient queue in Module F-7. This module names the pattern directly and generalizes it.

Converging Pointers

The shape: one pointer starts at the left end, one starts at the right end, and they move toward each other, each step ruling out one element from further consideration.

Two Sum on a sorted array is the cleanest illustration, and it's worth contrasting directly with the hash map version from Module F-4:

typescript

// Requires a sorted array. O(n) time, O(1) extra space — no hash map needed.
function twoSumSorted(nums: number[], target: number): [number, number] | null {
  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++;  // sum too small — the only way to increase it is a bigger left value
    else right--;                // sum too large — the only way to decrease it is a smaller right value
  }

  return null;
}

This works because the array is sorted: if the current pair sums too small, moving right inward can only make the sum smaller too (or equal) — the only direction that can help is increasing left. That single fact lets each pointer move only inward, never backward, so the two pointers together make at most n total steps — O(n), and critically, O(1) extra space, unlike Module F-4's hash-map version, which trades O(n) space for not needing the array sorted in the first place. This is a genuine trade-off, not a strictly better algorithm: sort cost (O(n log n), Modules P-9/P-10) versus hash map space, depending on what you're given and what you can afford.

Container With Most Water — given a set of vertical lines, find the two that trap the most water between them — uses the same converging shape, but the "which pointer moves" rule is different:

typescript

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

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

    // The shorter line is the bottleneck — moving it is the only move that could improve the area.
    // Moving the taller line can only shrink the width without raising the limiting height.
    if (heights[left] < heights[right]) left++;
    else right--;
  }

  return best;
}

The reasoning that justifies moving the shorter side is worth sitting with: the water trapped between any two lines is capped by the shorter one, regardless of how tall the other is. Keeping the taller line and discarding the shorter one can never produce a better answer than what you've already measured — every option that keeps that shorter line is strictly worse or equal, so it's always safe to move past it. This is what makes the two-pointer approach O(n) instead of checking every pair — O(n²).

Sort Colors (the Dutch national flag problem) is a three-way partition using three pointers instead of two, in a single left-to-right pass:

typescript

// Sort an array of 0s, 1s, and 2s in place, in a single pass
function sortColors(nums: number[]): void {
  let low = 0, mid = 0, high = nums.length - 1;

  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 here — the swapped-in value hasn't been checked yet
    }
  }
}

low tracks the boundary of confirmed 0s, high tracks the boundary of confirmed 2s, and mid scans forward — one pass, O(n) time, O(1) space, no separate counting step. This exact three-way-partition shape is also the core of quicksort's partitioning step, covered in full in Module P-10.

Fast/Slow Pointers

A different two-pointer shape: both pointers start at the same place and move at different speeds — typically one step at a time versus two steps at a time.

typescript

// Find the middle element of an array in one pass, without knowing the length up front
function findMiddle(nums: number[]): number {
  let slow = 0;
  let fast = 0;

  while (fast < nums.length - 1 && fast + 1 < nums.length - 1) {
    slow += 1;
    fast += 2;
  }

  return nums[slow];
}

By the time fast has covered the whole array, slow — moving at half the speed — is sitting exactly at the midpoint. Applied to a linked list (Module P-2), this same fast/slow relationship is the standard way to find the middle node in a single pass, without first counting the list's length in a separate pass.

The more well-known application is cycle detection — Floyd's algorithm, previewed here and covered in full once linked lists are introduced in Module P-2: if a fast pointer (two steps) and a slow pointer (one step) ever land on the same node again after starting together, the structure they're traversing contains a cycle. If there's no cycle, the fast pointer simply reaches the end first, with nothing further to check. The reasoning is a bit like two runners on a circular track at different speeds — the faster one is guaranteed to eventually lap the slower one if the track loops, and if it doesn't loop, the faster runner just finishes first.

Why Two Pointers Beats Nested Loops

The common thread across every example above: a plain nested loop checking every pair is O(n²), because it revisits combinations that a single, informed pass can rule out permanently. Two pointers work specifically when the data has some exploitable structure — sortedness (Two Sum sorted, Container With Most Water) or a known relationship between traversal speeds (fast/slow) — that lets you discard a whole set of possibilities with one comparison, instead of checking them individually.

typescript

// The nested-loop version this pattern replaces — O(n²)
function twoSumSortedSlow(nums: number[], target: number): [number, number] | null {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
  return null;
}

Recognizing "this data is sorted, or I can sort it cheaply" is often the first signal that a two-pointer solution exists where a nested loop currently sits.

Where This Shows Up in Your Stack

Deduplicating a sorted array in a single pass (advance a "write" pointer only when the current value differs from the last one written) is the in-memory version of what PostgreSQL's DISTINCT does over sorted or indexed input — removing adjacent duplicates without a separate hash-based pass.
Partitioning, as seen in sortColors, is the literal inner loop of quicksort (Module P-10) — every partitioning step during a quicksort run is this exact three-pointer (or two-pointer, in the classic Lomuto/Hoare variants) pattern applied to a subarray.
Cycle detection in linked lists (Module P-2) matters beyond puzzles — a corrupted or accidentally self-referential linked structure (a misconfigured parent/child relationship, a broken next pointer during a refactor) can cause infinite loops in code that walks the structure; Floyd's algorithm is the standard, O(1)-space way to detect that before it happens.
Rate limiting and windowed comparisons: many "compare the current window to the previous window" patterns in stream processing are a two-pointer relationship in disguise — one pointer tracking the current position, another tracking a fixed or sliding offset behind it, which Module F-9 develops into its own dedicated pattern.

Summary

Converging pointers (one from each end, moving inward) solve problems where sortedness or a similar structural property lets you safely discard one end's remaining possibilities on each comparison — Two Sum on sorted input, Container With Most Water, and three-way partitioning (Sort Colors) all follow this shape.
Fast/slow pointers (same start, different speeds) find midpoints in one pass and detect cycles — the exact mechanism behind Floyd's cycle detection, fully developed once linked lists are introduced.
The pattern beats nested loops because it exploits structure — sorted order or a known speed relationship — to rule out whole ranges of possibilities per step, turning O(n²) into O(n).
This shows up directly in production code: deduplication, quicksort's partition step, and cycle-safety checks on linked structures all lean on exactly this technique.

The next module, Sliding Window Pattern, extends the same "avoid recomputing from scratch" instinct from this module and Module F-7's moving average into a formal technique for substring and subarray problems with a constraint.

Knowledge Check

In twoSumSorted, why is it always safe to move the left pointer forward when the current sum is smaller than the target, without ever needing to check smaller values of right first?

In maxArea (Container With Most Water), why is it always safe to discard the shorter of the two current lines and move its pointer inward, rather than the taller one?

According to the module, what specific property must generally hold for a two-pointer approach to correctly replace a nested-loop, all-pairs comparison?

Test your knowledge with more question sets

Sign in to keep reading

The rest of this module is free — sign in with Google to unlock it and track your progress.

PreviousModule F-7: Queues: FIFO, Circular Queues, and Job Scheduling Next Module F-9: Sliding Window Pattern

Discussion

Join the discussion

Loading comments...