Week 2: Two Pointers

Pattern family: Foundational · Time budget: 12 hours · Prerequisites: Week 1 done (Arrays and Hashing, with the space-for-time trade and one-pass scanning fresh). · Cold-revisit obligation: Two Sum, Valid Anagram.

Overview

Two pointers is the second foundational pattern, and it is the cheapest one you own: it usually buys you O(1) extra space where a hash structure would have cost O(n). The whole idea is to track a position with two indices instead of one, and move them under a rule that lets you skip work you would otherwise repeat. The two indices most often start at opposite ends of a sorted array and walk toward each other; sometimes they both start at the left and one runs ahead of the other.

The lever is that on a sorted (or otherwise monotonic) structure, the value at each pointer tells you which pointer to move. If a pair sums too high, the only way to lower the sum is to pull the right pointer left; if too low, push the left pointer right. Each step rules out a whole batch of pairs at once, so a scan that looks O(n^2) collapses to O(n). The reflex to train this week fires before you write code: when the input is sorted (or you are allowed to sort it) and the question is about a pair or triple satisfying a relation, reach for two indices, not a nested loop.

flowchart TD
    Q["Read the problem"] --> A{"Is the input sorted, or am I<br/>allowed to sort it, and is the<br/>question about a pair or triple<br/>satisfying a relation?"}
    A -->|yes| H["Two pointers: put one index at<br/>each end, move under a rule.<br/>O(n) time, O(1) extra space."]
    A -->|no| B{"Is there a 'walk from both ends<br/>toward the middle', or a 'one index<br/>runs ahead of another' structure?"}
    B -->|yes| H
    B -->|no| C["Probably a different pattern.<br/>Keep reading the cues."]

Notice: the decision happens before you code, and it hinges on order. The directional rule that makes two pointers correct only exists on a sorted or monotonic structure; naming that out loud (principle 1) is what makes this diagram fire under pressure.

Warm-Up: Retrieve Before You Begin

Answer from memory, no peeking. This pulls forward the Week 1 and Week 0 tools that two pointers leans on hardest.

From Week 1: Two Sum on an unsorted array was solved with a hash map in O(n) time. What did that cost you in space, and why?
From the Week 0 refresher: what is the difference between a.sort() and sorted(a), and what does a.sort() return?
From the Week 0 refresher: what does a, b = b, a do, and why does it not need a temporary variable?

Check your recall

1. The hash-map Two Sum costs O(n) extra space, because it stores every value seen so far (mapped to its index) so that each complement lookup is O(1). That is the space-for-time trade from Week 1: you buy the single pass with a linear-size map. This week's contrast is direct: on a *sorted* array, two pointers solve the same shape in O(n) time and O(1) space, with no map at all. 2. `a.sort()` sorts the list in place and returns `None`; `sorted(a)` leaves `a` untouched and returns a new sorted list. The classic bug is `a = a.sort()`, which sets `a` to `None`. Use `a.sort()` when you may mutate the input, `sorted(a)` when you must preserve it. 3. `a, b = b, a` swaps the two names in one statement. The right-hand side `b, a` is packed into a tuple first, then unpacked into the left-hand names, so the old values are both captured before either name is rebound; no temporary is needed.

Learning objectives

By the end of this week you can:

Recognize the two-pointer cue (sorted or sortable input, a question about pairs or triples, or a “walk from both ends” structure) and reach for two indices without being told.
State the directional rule for an opposite-ends scan: which pointer to move when the current pair overshoots or undershoots the target, and why moving it is safe.
Construct an opposite-ends two-pointer solution that runs in O(n) time and O(1) extra space where a naive approach would be two nested loops.
Apply the sort-then-fix-then-two-pointer template to 3Sum, including skipping duplicates correctly at all three levels.
Analyze the time and space complexity of your solution and name what dominates at scale, including when a sort is the dominating term.
Defend every line of each solution you commit, from memory, with no AI open, including why each pointer move cannot skip a valid answer.

Recognition cue

“The input is sorted (or I am allowed to sort it), and the question is about a pair or triple that satisfies a relation” almost always means two pointers. The other surface form is any “walk from both ends toward the middle” structure: checking a palindrome, or pinching inward on a container. A third form, which returns in Week 6, is the fast/slow variant where both pointers start at the left and one advances faster than the other (finding a cycle, or the middle of a linked list). The common thread is two positions moving under a rule, replacing a loop that would otherwise rescan.

Core concepts to internalize this week

Why sorting is often step one. The directional rule depends on order: on a sorted array, a larger sum is always to the right and a smaller sum to the left, so the value at a pointer tells you which way to move. If the problem does not hand you sorted input but does not need original indices, sorting first (O(n log n)) to unlock an O(n) two-pointer scan is a standard and often winning move. The cost is the sort and the loss of original positions.
The directional rule, made precise. With one pointer at each end of a sorted array, compute the current pair’s sum. If it equals the target, you found it. If it is too small, the left pointer must move right (every pair using the current left element and a smaller right element is also too small, so they are all ruled out). If it is too large, the right pointer must move left, by the mirror argument. Each move discards a whole row or column of the implicit pair grid; that is why the scan is linear.
The “shorter side moves” intuition (Container With Most Water). The area between two lines is min(left_height, right_height) * width. Moving the taller side inward can only shrink the width while keeping the height capped by the shorter side, so it cannot help. Moving the shorter side is the only move that can find a taller limiting wall, so that is the move you make. State this argument out loud; it is the correctness proof, not a heuristic.
Two pointers as a special case of sliding window. A sliding window (Week 3) is two indices, a left and a right, that both move left-to-right and bound a contiguous range. The opposite-ends two-pointer scan is the variant where the indices start apart and close in. Seeing them as the same family (“two indices moving under a rule”) is what makes Week 3 feel like a continuation rather than a new idea.
Skipping duplicates with index moves. When the input is sorted and the problem wants distinct results (3Sum), equal values sit next to each other. After you commit to a value or record a result, advance the index past every copy of that value (while lo < hi and nums[lo] == nums[lo - 1]: lo += 1). This is how you avoid duplicate triples without a set.
The fast/slow variant (a forward pointer). Not every two-pointer problem starts at the ends. Some keep a slow pointer marking where the next kept element goes while a fast pointer scans ahead (in-place dedup, moving zeroes). Week 6 returns to the fast/slow pair for cycle detection in linked lists; note the shape now so it is familiar then.

Common misconception. “Opposite-end two pointers works on any array; you just put a pointer at each end and walk in.” Reality. The directional rule (move the left pointer when the sum is too small, the right when it is too large) is only valid when the structure is sorted or otherwise monotonic. On an unsorted array, a smaller sum is not guaranteed to be on the left, so moving a pointer can skip the answer. This is exactly why 3Sum sorts first: the sort is what licenses the inward walk. If you cannot sort and cannot establish monotonicity, two pointers is the wrong reach.

Common misconception. “In Container With Most Water, I should move whichever pointer I like, or always the left one.” Reality. You must move the pointer at the shorter line. The area is capped by the shorter side, so moving the taller side inward can only keep that cap and shrink the width, never improving the result; only moving the shorter side can find a taller wall. Moving the wrong pointer does not just slow you down, it can walk straight past the best answer. Knowing which pointer and why is the whole problem.

Python idioms this week

You are not yet expected to be fluent, so here is the toolbox this week uses. If any is unfamiliar, open the Python refresher before Monday.

A two-index while loop: i, j = 0, len(arr) - 1 then while i < j:, moving i += 1 or j -= 1 inside. This is the spine of every problem this week.
arr.sort() (in place, returns None) versus sorted(arr) (returns a new list). Use the in-place sort when you are allowed to reorder the input and do not need original indices.
The swap a, b = b, a, and tuple unpacking generally (lo, hi = i + 1, n - 1).
Skipping duplicates by advancing an index in a while: while lo < hi and nums[lo] == nums[lo - 1]: lo += 1.
String inspection for palindromes: ch.isalnum() (is this character a letter or digit?) and ch.lower() (case-fold one character). These let you compare two ends of a string while ignoring punctuation and case, without building a cleaned copy.
min(...) and max(...) over the current pair, for area-style and water-style problems.

These are tools you are allowed to know cold in an interview. The pattern (which pointer moves, and why that move is safe) is the part you build yourself.

Pattern Card requirement

Before you solve the canonical problem, write your Pattern Card at .tutor/pattern-cards/two-pointers.md. It must contain:

The recognition cue, in your own words.
The algorithmic skeleton in pseudocode (the opposite-ends scan: two indices, the directional rule, the loop condition).
Time and space complexity, general form (and when a sort makes O(n log n) the dominating term).
Three edge cases (empty input, a single element, and all-equal or all-duplicate values are good starts).
One war story (a bug you actually hit this week); fill this in at the end of the week.

The first four sections must be present before you start the canonical deep-dive. The tutor will probe the card; it will not write any of it for you.

Canonical deep-dive

Problem: 3Sum (https://leetcode.com/problems/3sum/)

3Sum is this course’s home for the full two-pointer machinery: sort the array, fix one index, two-pointer the remainder for the complement, and skip duplicates correctly at all three levels. The full guided walk-through, with the approach, the exact complexity, and the key insight, is in canonical/3sum.md. Work it there. You will implement it yourself, in your own work repo, and write a short debrief. The walk-through is deliberately not an answer key: it shows you how to think, and stops short of code you could paste.

Practice set

Four problems, in this order. Each has its own folder under practice/ with the problem link, a complexity target for you to fill in, and the debrief template. Do not skip ahead.

Valid Palindrome (practice/valid-palindrome/). The simplest opposite-ends walk: two indices closing in, skipping non-alphanumeric characters and comparing case-folded. No sorting needed; the string order is the structure.
Container With Most Water (practice/container-with-most-water/). The “shorter side moves” problem. Prove to yourself why moving the taller side can never help.
Trapping Rain Water (practice/trapping-rain-water/). Two pointers carrying a running left-max and right-max. The hardest of the four; the invariant is the lesson.
Two Sum II (practice/two-sum-ii/). The sorted version of Week 1’s Two Sum, solved with two pointers in O(1) space. This is the direct space-for-time contrast with the hash-map solution you wrote last week.

Each problem follows the five-beat rhythm.

The five-beat rhythm (every problem)

Pattern Card is written (you did this Monday).
Name the pattern aloud and write your approach as a plain-English comment before any code.
Struggle floor: 25 minutes unaided.
Hint ladder if needed: six rungs, one per ask.
Debrief: the five questions, in your commit message, before the next problem.

Reflect

Ten minutes in your notebook, in writing:

Explain it back: describe the directional rule for an opposite-ends scan to a peer who just finished Week 1, in three sentences: what you compute, which pointer moves when, and why that move cannot skip the answer.
Connect: Two Sum II is Two Sum on a sorted array. Week 1’s hash-map solution was O(n) time and O(n) space; this week’s two-pointer solution is O(n) time and O(1) space. What did sorting buy you, and what would you have to pay to sort an unsorted input first?
Monitor: which is still fuzzy, the directional rule for sums, or the “shorter side moves” rule for Container? Write the one sentence that would clear it up.

Knowledge Check

Answer from memory first. Items marked ⟲ are spaced callbacks to earlier material.

State the directional rule for an opposite-ends two-pointer scan on a sorted array: when do you move the left pointer, when the right, and why is each move safe?
In 3Sum, you skip duplicates at three places. Name all three and say what each one prevents.
In Container With Most Water, which pointer do you move and why is moving the other one provably useless?
⟲ From Week 1: Two Sum on an unsorted array uses a hash map for O(n) time. Two Sum II (sorted) uses two pointers. Compare their space costs and say what makes the two-pointer version possible.
⟲ From Week 0: what does a, b = b, a do under the hood, and why does it not need a temporary variable?

Answer key

1. Compute the current pair's sum. If it equals the target, you found a pair. If it is too small, move the left pointer right: every pair using the current left element with a still-smaller right element is also too small, so they are all ruled out. If it is too large, move the right pointer left, by the mirror argument. Each move discards a whole batch of pairs at once, so no valid pair is skipped and the scan is linear. 2. (a) The fixed index `i`: skip it if `nums[i] == nums[i - 1]`, so you do not start a triple from a value you already used as the anchor. (b) The left pointer `lo` after recording a triple: advance past every copy of `nums[lo]`, so you do not record the same triple again with an identical left value. (c) The right pointer `hi` after recording a triple: advance past every copy of `nums[hi]`, for the same reason on the right. Together they yield only distinct triples without needing a set. 3. Move the pointer at the shorter line. The area is `min(left, right) * width`; moving the taller side inward keeps the height capped by the shorter side and only shrinks the width, so it can never increase the area. Only moving the shorter side can find a taller limiting wall, so it is the sole move that can improve the answer. 4. The hash-map Two Sum is O(n) time and O(n) space (it stores every value seen). The two-pointer Two Sum II is O(n) time and O(1) space. The two-pointer version is possible only because the array is sorted: the directional rule needs order to know which pointer to move. On an unsorted array you would have to sort first (O(n log n)) or fall back to the hash map. 5. The right-hand side `b, a` is packed into a tuple, then unpacked into the left-hand names `a, b`. Both old values are captured in the tuple before either name is rebound, so the swap is correct without a temporary variable.

Cold revisit

This Friday, before any new work, re-solve two prior problems cold: no notes, no prior code open, no AI, the standard 25-minute floor on each. The full instructions are in revisit.md.

Two Sum (Week 1, Arrays and Hashing). A blind re-solve.
Valid Anagram (Week 1, Arrays and Hashing). A blind re-solve, same rules.

Both are hashing problems, not two-pointer problems, and that is deliberate: the cold revisit trains recognition across the whole course, not just this week’s pattern. (Two Sum in particular is worth re-feeling now, because this week’s Two Sum II is the same question on sorted input with a different pattern; notice how the cue changes.) Debrief each at the end and log the outcome in .tutor/revisit-log.md.

How to know you are done with this week

Pattern Card complete at .tutor/pattern-cards/two-pointers.md, including the war-story field.
Canonical deep-dive done: 3Sum implemented yourself, with your short debrief (in your work repo).
Four practice problems solved, each with a five-question debrief in its commit message.
.tutor/revisit-log.md updated by the tutor with this week’s problems and the two cold revisits (Two Sum, Valid Anagram), with dates.
.tutor/progress.md updated to “Week 2 complete; ready for Week 3.”

If any of the above is missing, the week is not done. The tutor will not advance you to Week 3 until all five are present.

Resources

Free, no account required:

[Article] Two pointers technique, the idea: https://en.wikipedia.org/wiki/Two-pointer_technique
[Docs] Python list.sort and sorted: https://docs.python.org/3/howto/sorting.html
[Docs] Python string methods (str.isalnum, str.lower): https://docs.python.org/3/library/stdtypes.html#string-methods