λDSA Learning Hubpart of DSA Atlas

Two Pointers

Intermediate~2h · 5 lessons12 practice problems

Two indexes replacing nested loops: converging ends on sorted data, read/write partitioning, and fast/slow traversal — O(n²) → O(n).

0 of 5 lessons checked off

Introduction

What it is

  • Two pointers is a family of one-pass techniques where two indexes traverse a sequence under coordinated rules instead of independently (which would be a nested loop).
  • Three shapes cover the family: converging (ends walking inward on sorted data), read/write (fast reader, slow writer for in-place filtering), and fast/slow (different speeds, mostly on linked lists).

Why it matters

  • It's the most common O(n²) → O(n) upgrade in interviews: pair sums, palindromes, container-with-most-water, remove-duplicates all fall to it.
  • The technique costs O(1) space, which is why 'in place' and 'constant space' prompts almost always mean pointers.

How it works

  • Converging: sortedness gives a monotonic lever — sum too small? only moving LEFT up can help; too big? only RIGHT down. Each step permanently discards candidates.
  • Read/write: reader scans every element; writer marks the boundary of the 'kept' prefix. Invariant: everything left of writer is final.
  • Every variant's correctness is an invariant plus a proof that each step makes irreversible, safe progress.

Where it's used

  • Merging sorted files, deduplicating sorted logs, meeting-point problems, and the partition step inside quicksort are all pointer walks.

In interviews

  • Two Sum II (sorted), 3Sum, valid palindrome, container with most water, move zeroes, remove duplicates, trapping rain water (two-pointer variant).
Analogy: Two people searching a sorted bookshelf from opposite ends for two books whose combined weight hits a target: too light — the left person steps right; too heavy — the right person steps left. Nobody ever backtracks.

Interactive diagram

Sum too small moves L right; too big moves R left. Every step discards provably useless candidates.

Start at both ends

The array is sorted, so the smallest candidate sum uses left and the largest uses right. Target: 10.

target
10

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. Converging pointers on sorted data

    Pair sum, the discard argument, and why sortedness is required.

    25 min
  2. Read/write pointers (in-place filtering)

    Remove duplicates / move zeroes with the 'finalised prefix' invariant.

    25 min
  3. Fast and slow pointers

    Middles and cycles — covered deeply on the linked-list page.

    20 min
  4. 3Sum: fixing one, converging two

    Sorting + outer loop + converging inner pair, with dedup discipline.

    30 min
  5. Container with most water

    Move the shorter wall — the exchange argument in action.

    20 min

Operations

Converging pair sum

Start at both ends of sorted data; the comparison tells you which pointer can possibly help.

Start at both ends

The array is sorted, so the smallest candidate sum uses left and the largest uses right. Target: 10.

target
10
def pair_sum_sorted(nums: list[int], target: int) -> list[int]:    """Indices of two values summing to target in SORTED nums. O(n)/O(1)."""    left, right = 0, len(nums) - 1    while left < right:        total = nums[left] + nums[right]        if total == target:            return [left, right]        if total < target:            left += 1        # only a bigger left value can raise the sum        else:            right -= 1       # only a smaller right value can lower it    return []
Time: O(n)Space: O(1)

Edge cases

  • Unsorted input: sort first (losing original indexes — track them if needed) or use a hash map instead.
  • left < right, not <=: an element can't pair with itself.
  • No pair: pointers cross, return the sentinel.

Common mistakes

  • Applying it to unsorted data — the discard logic is meaningless there.
  • Moving both pointers on a non-match, skipping valid pairs.

Read/write partitioning (move zeroes)

Reader visits every element; writer receives only the keepers. The prefix left of writer is always the final answer so far.

Read/write partitioning (move zeroes)
def move_zeroes(nums: list[int]) -> None:    """All non-zeros first (order kept), zeros after. In place, O(n)."""    write = 0    for read in range(len(nums)):        if nums[read] != 0:            nums[write], nums[read] = nums[read], nums[write]            write += 1    # invariant held throughout: nums[:write] is exactly the non-zeros seen,    # in their original order
Time: O(n)Space: O(1)

Edge cases

  • All zeros / no zeros: loop degenerates gracefully.
  • The swap (not overwrite) preserves the zeros without a second fill pass.
  • Relative order of non-zeros is preserved — a stated requirement in the classic problem.

Common mistakes

  • Advancing write on every read step, which just copies the array onto itself.
  • Nested-loop shifting per zero: the O(n²) this pattern replaces.

Complexity analysis

OperationBestAverageWorstSpace
Converging pair searchO(1)O(n)O(n)O(1)
Read/write filterO(n)O(n)O(n)O(1)
3Sum (sort + converge per anchor)O(n²)O(n²)O(n²)O(1)
Nested-loop equivalentO(n²)O(n²)O(n²)O(1)

The pattern's pitch in one row pair: pointer walks do in O(n) what nested loops do in O(n²) — when a monotonic discard argument exists.

Python implementation

Production-quality code with type hints, validation, and docstrings.

3Sum: the anchor + converge template
def three_sum(nums: list[int]) -> list[list[int]]:    """All unique triplets summing to zero. O(n^2) time, O(1) extra."""    nums.sort()    result: list[list[int]] = []    n = len(nums)    for i in range(n - 2):        if nums[i] > 0:            break                        # sorted: no zero-sum possible ahead        if i > 0 and nums[i] == nums[i - 1]:            continue                     # skip duplicate anchors        left, right = i + 1, n - 1        while left < right:            total = nums[i] + nums[left] + nums[right]            if total < 0:                left += 1            elif total > 0:

What interviewers expect you to know

Recognition signals

  • Sorted array (or sortable without penalty) + pair/triplet condition → converging.
  • 'In place', 'O(1) space', 'remove/compact/partition' → read/write.
  • Linked list + middle/cycle/kth-from-end → fast/slow.

What you must be able to prove

  • The discard argument: when sum < target, NO pair using the current left can work (right is already the maximum available) — so left++ is safe, not heuristic.
  • The read/write invariant: 'nums[:write] is the final answer for everything read so far.'

Classic follow-ups

  • "Return indexes of the ORIGINAL array" after sorting — decorate with (value, index) pairs first.
  • "What if it's unsorted and you can't sort?" — hash-map complements (two-sum) replace the pattern.
  • "Count pairs instead of finding one" — on equality, count runs of duplicates on both sides.

Common mistakes

Pointers on unsorted data

Converging correctness rests entirely on sortedness. No order, no discard argument, no algorithm.

Dedup skipped in 3Sum

Without all three adjacent-equal guards the output contains duplicate triplets — an automatic follow-up question you want to preempt.

left <= right in pair search

Allows an element to pair with itself. The strict inequality is load-bearing.

Moving the wrong pointer in container-with-water

Always move the SHORTER wall: the width shrinks either way, and only a taller short wall can improve area.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Easy (4)

Medium (7)

Hard (1)

Topic quiz

4 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Concept1. In converging pair-sum, sum < target justifies left++ because…
  2. Code output2. After move_zeroes([0, 1, 0, 3, 12]) the array reads…
  3. Complexity3. 3Sum with sorting + converging pairs runs in…
  4. Scenario4. 'Remove all occurrences of val in place and return the new length.' Which shape?
0 of 4 answered

Frequently asked questions

Two pointers or hash map for pair problems?

Sorted input (or sorting allowed): pointers — O(1) space. Must preserve positions on unsorted input: hash map — O(n) space, one pass. Interviews often want you to name both and choose by constraints.

Is sliding window just two pointers?

It's the contiguous-subarray specialisation: both pointers move the same direction and the window between them carries maintained state. Different invariant, own page — but yes, same family.

Summary & cheat sheet

Key takeaways

  • Three shapes: converging (sorted pairs), read/write (in-place filters), fast/slow (lists).
  • Correctness = invariant + irreversible-safe-discard argument.
  • kSum = anchors + one converging pair; dedup by adjacency after sorting.
  • 'In place / O(1) space' is the prompt's way of saying 'pointers'.

Formulas & cheat sheet

  • Converging walk: exactly n − 1 pointer moves worst case
  • 3Sum: O(n²) time, output up to Ω(n²) triplets

Interview checklist

  • I can state the discard proof for converging pointers.
  • I can write move-zeroes with the writer invariant.
  • I can produce duplicate-free 3Sum output first try.