Lesson 2 of 8 · 48 min

Two pointers on arrays and lists

Opposite-end, same-direction, and fast/slow pointer families — invariants, complexity, production metaphors (stream merge, retry loops), and 3Sum discipline.

When sorted input unlocks linear time

Nested loops feel “correct” to builders because they mirror nested for-each in production. Interviewers plant sorted arrays and linked lists precisely to see whether you notice that two indices moving with a rule collapse O(n²) into O(n). Two pointers is not one trick — it is a family: opposite ends, same-direction (fast runner), and fast/slow on lists. Production metaphors you already know: merging sorted event streams, detecting a loop in a retry queue, finding a midpoint without knowing length.
Pattern recognition starts with the input shape. Sorted array + pair / partition question → try opposite-end two pointers. Need each element once in order with a write head → same-direction pointers (remove duplicates, partition). Linked list + cycle / middle / kth-from-end → fast & slow. Saying the family name in the first minute is a Problem Solving signal; coding nested loops on a sorted array is a ding you narrate yourself out of: “brute force is O(n²); because sorted I can do better.”
Complexity literacy: opposite-end two pointers on a sorted array is typically O(n) time, O(1) extra space after sort if needed (sort costs O(n log n)). Fast/slow is O(n) time, O(1) space. Always state both. If the interviewer cares about index stability or “do not modify input,” space and approach change — clarify before committing.

Opposite ends: pair sums, containers, 3Sum skeleton

Two Sum II (1-indexed sorted array): left at start, right at end; move the side that fixes the sum. Container With Most Water: area = min(h[l],h[r]) * (r−l); move the shorter side because width only shrinks — the only hope is a taller min. 3Sum: sort, fix outer i, then two-pointer the pair that sums to −nums[i], skipping duplicates. Narrate the invariant: “everything left of L is too small to help; everything right of R is too large.”
python
1OPPOSITE ENDS — Container With Most Water (narrate the move rule)23def max_area(height: list[int]) -> int:4    l, r = 0, len(height) - 15    best = 06    while l < r:7        best = max(best, min(height[l], height[r]) * (r - l))8        # Move the shorter side — width shrinks, only taller min can improve.9        if height[l] < height[r]:10            l += 111        else:12            r -= 113    return best1415# Dry-run [1,8,6,2,5,4,8,3,7]: start ends 1 and 7; move left (shorter) toward 8…16# Complexity: O(n) time, O(1) space — say it before coding.
Production metaphor: merging two sorted event streams by timestamp is opposite/same hybrid — you always advance the stream with the earlier head (like merge step of merge-sort). Interviewers love “merge two sorted lists/arrays” because it is two pointers with an obvious production story. Name the story: “same as merging sorted Kafka offsets for a user’s timeline.”

Same-direction: compact, partition, remove

Same-direction pointers share a read index and a write index. Example: remove duplicates from sorted array in-place — write unique prefix; read scans forward. Partition array by predicate (Dutch national flag is three pointers). The invariant: nums[0:write] is the answer so far; read ≥ write. This is how you rewrite filters without allocating — interviewers listen for that production parallel.
python
1SAME-DIRECTION — remove duplicates from sorted array (in-place)23def remove_duplicates(nums: list[int]) -> int:4    if not nums:5        return 06    w = 1  # next write position7    for r in range(1, len(nums)):8        if nums[r] != nums[w - 1]:9            nums[w] = nums[r]10            w += 111    return w  # new length; nums[:w] unique sorted1213# Invariant: nums[:w] is compacted unique prefix.14# O(n) time, O(1) extra space.

Fast & slow: cycle, middle, kth-from-end

On a linked list, you rarely know n. Fast advances two steps, slow one. Cycle detection (Floyd): if they meet, there is a cycle; to find entrance, reset one pointer to head and advance both one step until meet. Middle: when fast hits end, slow is mid (careful even/odd). Remove Nth from end: advance fast n+1, then move both until fast is None — slow is before the node to delete. Production metaphor: detecting a loop in a retry/next-pointer graph without allocating a visited set of size n.
python
1FAST/SLOW — has cycle (Floyd). O(1) space vs hash set of nodes.23class ListNode:4    def __init__(self, val=0, next=None):5        self.val, self.next = val, next67def has_cycle(head: ListNode | None) -> bool:8    slow = fast = head9    while fast and fast.next:10        slow = slow.next11        fast = fast.next.next12        if slow is fast:13            return True14    return False1516# Dry-run: acyclic 1→2→3→None: fast hits None. Cyclic 1→2→3→2: eventually meet.17# Why it works: relative speed 1 closes the gap in a loop.
Interview narration for cycle: “I could store seen node ids in a set — O(n) space. Floyd uses constant space by relative speed. If you need the entrance, I know the reset trick; want me to implement it?” Offering the tradeoff without being asked is senior Problem Solving.

3Sum: where two pointers meet sorting discipline

3Sum is medium because of duplicate skipping, not because the two-pointer core is hard. Sort first. For each i, skip if nums[i]==nums[i-1]. Left,right find pairs summing to −nums[i]; when you find a pair, skip duplicate left/right values. Complexity O(n²) time after O(n log n) sort. State that clearly. Common bug: moving only one pointer after a hit, or forgetting to skip duplicates → wrong counts or TLE on sorted runs of equals.

Complexity and failure modes you must narrate

Opposite-end after an O(n log n) sort is O(n log n) total — say that, do not claim O(n) if you sorted. Fast/slow is O(n)/O(1) vs visited-set O(n)/O(n); pick based on space budget. Same-direction in-place is O(n)/O(1) but mutates input — ask permission. Off-by-one on while l < r vs l <= r is the most common live bug: dry-run a two-element array every time.
When the interviewer twists the problem (“return all pairs,” “array not sorted,” “linked list instead of array”), re-classify the family out loud before rewriting. Silent rewrites look like panic. A 20-second reframe saves the Problem Solving score.
Container With Most Water — NeetCodeNeetCode

Interview prep

Pointer rounds test whether you name the family, the invariant, and the complexity before indexes fly. Pre-answer these out loud while tracing on paper.
  1. 01“When do you use two pointers?” → sorted pair/partition problems; same-direction compact; fast/slow on lists for cycle/mid/kth.
  2. 02“Why move the shorter line in Container With Most Water?” → width always shrinks; only a taller min(height) can improve area.
  3. 03“Cycle detection without O(n) memory?” → Floyd fast/slow; relative speed guarantees meet if cycle exists.
  4. 04“Remove Nth from end in one pass?” → lead pointer by n (or n+1 with dummy head), then advance both.
  5. 05“3Sum duplicates?” → sort + skip equal outer and equal inner pointers after a hit.
  6. 06“Sorted vs hash for Two Sum?” → need indices on unsorted → hash; sorted Two Sum II → two pointers O(1) space.
  7. 07“Production story?” → merge sorted streams; detect retry loop; compact filtered buffer in place.
  8. 08“Complexity you must say?” → usually O(n)/O(1); 3Sum O(n²)/O(1) or O(log n) if sort space counts.
  9. 09"Trapping rain without O(n) arrays?" -> two pointers + maxLeft/maxRight; resolve smaller side.
  10. 10"Dutch flag invariant?" -> [0,low) zeros, [low,mid) ones, (high,n] twos.
  11. 11"Merge sorted arrays from end?" -> write pointer must not overwrite unread values.
  12. 12"Cycle II one-liner?" -> head-to-entrance equals meeting-to-entrance along cycle; reset equalizes.
State the invariant before the while-loop. If you cannot say what is true of L and R at every iteration, you are guessing moves — and dry-runs will fail.
articleTwo Pointers pattern — AlgoMasterAlgoMasterdocsNeetCode practice roadmapNeetCodearticleFloyd cycle detection — WikipediaWikipediaarticleTech Interview Handbook — coding patternsTech Interview Handbook

Senior aloud answers + rain water / 3Sum code

1. Two Sum sorted: l/r converge; stream input forces hashmap instead. 2. 3Sum: fix + skip duplicates; O(n^2); trace [-1,0,1,2,-1,-4]. 3. Container: move shorter line only. 4. Trap rain: two pointers with maxLeft/maxRight vs prefix arrays — name space. 5. Palindrome: isalnum skip; empty/single valid. 6. Reverse list: prev/curr/next; concurrent readers break it. 7-8. Cycle / entrance: Floyd meet is not the entrance; phase-two reset finds entry. 9. Dutch flag / dedup II: three-way invariants; look-back-2 write. 10. Merge sorted in place: write from the end. Production metaphors: Stripe ledger merge, packet compact, Terraform cycle, Kafka offset vs high watermark — transfer the story, not the LC id. Force the move rule aloud: when the predicate fails I move X because...
python
1TRAPPING RAIN WATER — two pointers O(1) space23def trap(height: list[int]) -> int:4    if not height:5        return 06    l, r = 0, len(height) - 17    left_max = right_max = water = 08    while l < r:9        if height[l] < height[r]:10            if height[l] >= left_max:11                left_max = height[l]12            else:13                water += left_max - height[l]14            l += 115        else:16            if height[r] >= right_max:17                right_max = height[r]18            else:19                water += right_max - height[r]20            r -= 121    return water2223# Smaller side is safe to resolve: opposite side is a taller wall.24# Alt: prefix/suffix max arrays O(n) space — state both.
python
13SUM — sort + opposite ends + duplicate skip23def three_sum(nums: list[int]) -> list[list[int]]:4    nums = sorted(nums)5    n, out = len(nums), []6    for i in range(n):7        if i and nums[i] == nums[i - 1]:8            continue9        l, r = i + 1, n - 110        while l < r:11            s = nums[i] + nums[l] + nums[r]12            if s < 0:13                l += 114            elif s > 0:15                r -= 116            else:17                out.append([nums[i], nums[l], nums[r]])18                l += 1; r -= 119                while l < r and nums[l] == nums[l - 1]:20                    l += 121                while l < r and nums[r] == nums[r + 1]:22                    r -= 123    return out  # O(n^2) after O(n log n) sort
Graders + tiers. Communication: L/R invariant each loop. Problem Solving: opposite vs same-direction vs fast/slow; when sort is required. Coding: l<r vs l<=r; duplicate skips. Verification: empty, single, all-equal, two-element. FAANG: often a follow-up to brute ("now O(1) space"). India OA: sorted-array variants under time pressure. AI lab: on-disk sorted logs with RAM caps — modeling beats syntax. Dry-run a two-element array every time you write while l < r — off-by-one dies there.
articleTwo Pointers cheatsheet — TIHTech Interview Handbook

Checkpoint

Interviewer: sorted array of ints, find if any pair sums to T. You start writing a hash set. What is the stronger opening?

AHash set is always best for pair sums — continueBNote sorted: opposite-end two pointers O(n) time O(1) space; mention hash as alternative if unsortedCSort again (already sorted) then binary search for T−x for each x
Sign up free to answer and see why

Checkpoint

Dry-run cycle detection: list 1→2→3→4→2 (cycle at 2). Fast and slow start at 1. After enough steps they meet. Where?

AThey never meet because the cycle does not include the headBThey meet at some node on the cycle (e.g. 2, 3, or 4 depending on steps) — meeting proves a cycle existsCThey meet only at node 1
Sign up free to answer and see why

Checkpoint

Container With Most Water: height[l] == height[r] and l < r. Which move is safe?

AMust not move either pointer — stuck foreverBMove either pointer (or both); equality means neither side is uniquely limiting beyond the otherCAlways move both ends by 2 for speed
Sign up free to answer and see why

Checkpoint

You need the middle of a singly linked list of unknown length. Best approach in an interview?

ATraverse once to count n, traverse again to n//2BFast/slow pointers: when fast cannot advance two steps, slow is mid — mention even-length conventionCStore all nodes in an array then index mid
Sign up free to answer and see why

Checkpoint

3Sum returns duplicate triplets. Root cause in a typical two-pointer solution?

AUsing sort — sorting creates duplicatesBFailing to skip equal nums[i] / equal left / equal right after accepting a tripletCUsing O(n²) time — must use O(n) hash only
Sign up free to answer and see why

Can you pick opposite-end vs same-direction vs fast/slow on a fresh prompt and dry-run the invariant?

New to itGetting thereConfident

Takeaways

  • Three families: opposite ends (sorted pairs/areas), same-direction (compact/partition), fast/slow (lists).
  • Always state the invariant and complexity before the while-loop.
  • Sorted input is a gift — O(1) space two pointers often beats hash.
  • 3Sum difficulty is duplicate control, not the pointer mechanic.
  • Production bridges: merge streams, retry loops, in-place filter buffers.

Next: sliding window — fixed and variable windows, and the “at most K” template.

Sources

Free to read · better with Enzo

Learn it with Enzo

Save your progress, answer the checkpoints, and let Enzo quiz you on what you just read.

Continue with EnzoSign up free