Command Palette

Search for a command to run...

Hectal

Module 6

Two Pointers

Two indexes moving with a rule: from both ends towards the middle, or one reading and one writing. They turn O(n²) pair searches into O(n).

Beginner 3 lessons 7 problems ~35 min of lessons
Two Pointers: Opposite EndsTwo Pointers: Read and Write

Two pointers is the first pattern where a clever rule removes most of the work. In a sorted array, comparing the smallest and largest remaining values tells you which one can never be part of the answer, so you discard it and move on: every step eliminates a whole row of pairs.

You'll learn both forms (opposite ends, and read/write in the same direction), when to sort first, and how to skip duplicates. The module ends with Trapping Rain Water, a hard problem that becomes simple once the pointer rule is clear.

Best after: Arrays

Part 1

Learn the ideas

  1. 6.1Why Two Pointers WorkIn a sorted array, one comparison of the two ends rules out every pair involving one of them. That elimination is why O(n²) pairs shrink to O(n) steps.14 min
  2. 6.2Read and Write PointersFilter an array in place: the read pointer visits every element, the write pointer marks where the next kept element goes.10 min
  3. 6.3Sort First, and Skip DuplicatesWhen order doesn't matter, sorting (O(n log n)) unlocks two pointers; skipping equal neighbours avoids duplicate answers.12 min

Part 2

Solve the problems

In order of difficulty. Each one shows the pattern it teaches.

  1. 6.1Two Sum II: Sorted InputMediumTwo Pointers: Opposite Ends

    On sorted input, two pointers find a pair in O(n) time with O(1) space, beating the hash map's O(n) space.

  2. 6.2Move ZeroesEasyTwo Pointers: Read and Write

    Read/write pointers keep the non-zero elements in order at the front; the rest is filled with zeros.

  3. 6.3Remove Duplicates from Sorted ArrayEasyTwo Pointers: Read and Write

    Keep an element only if it differs from the last kept one: read/write pointers on sorted data.

  4. 6.4Squares of a Sorted ArrayEasyTwo Pointers: Opposite Ends

    The largest squares sit at the two ends; fill the result from the back by comparing ends.

  5. 6.53SumMediumTwo Pointers: Opposite Ends

    Sort, fix one element, two-pointer the rest, and skip duplicates at every level: O(n³) becomes O(n²).

  6. 6.6Container With Most WaterMediumTwo Pointers: Opposite Ends

    A greedy pointer rule with a proof: always move the shorter line, because the taller one can never do better with it.

  7. 6.7Trapping Rain WaterHardTwo Pointers: Opposite Ends

    Water above a bar is min(tallest on the left, tallest on the right) − its height. Prefix/suffix maxima give O(n); two pointers do it in O(1) space.