Two Pointers, Sliding Window and Prefix Sums (Java + Kotlin)

The linear-scan pattern family: how to coordinate two indices over a sequence so you never re-examine a decision already made, collapsing a nested-loop O(n²) into a single O(n) pass.

Series map: 00 playbook · 01 two pointers & sliding window (this file) · 02 binary search, stacks & intervals · 03 trees & graphs · 04 recursion & backtracking · 05 dynamic programming · 06 staff+ practical & OOD. Companion (non-series): data-structures-java-kotlin-study-guide.md — reach there for why a HashMap / ArrayDeque / PriorityQueue behaves as it does (internals, boxing, cache locality). This guide uses those structures as tools and spends its words on the algorithm.

The mental model#

Every technique here is one idea wearing seven costumes:

Maintain a contiguous region [left, right] of the sequence, advance right to admit new elements, advance left to retire old ones, and keep just enough state about what's between the pointers that each element is touched O(1) times.

Brute force asks a fresh question at every pair (i, j) — O(n²). Two pointers exploits monotonicity: some property changes predictably as the window moves, so a decision made at (i, j) tells you the answer for a whole range of neighbors, and you never back up. The pointers only ever move forward (or converge), so total work is O(n) even though there are two loops-worth of index motion — the inner while is amortized across the outer for.

The whole family is one axis of variation — what the region between the pointers means:

If you internalize "which of these does the region mean here, and what makes the move safe?" you will recognize the pattern from the problem statement before you write a line. That recognition is 80% of the interview.

A one-time Kotlin helper used throughout (Java inlines a three-line temp swap each time):

1. Two pointers — converging from opposite ends#

Recognition cue. Sorted array/string, or a symmetric task: find a pair/triplet summing to a target, reverse in place, is this a palindrome, container/area between two walls, partition into ≤/=/> buckets. If the input is sorted (or you're allowed to sort and indices don't matter), reach here first.

Why sortedness enables the move. With lo at the smallest candidate and hi at the largest, nums[lo] + nums[hi] is monotonic in each pointer: too small ⇒ the only way to grow the sum is lo++ (every element left of hi paired with the current lo is even smaller, so they're all eliminated at once); too big ⇒ hi--. Each step discards a whole row/column of the n² pair matrix. That is the entire trick.

Template (two-sum on a sorted array).

Reversing a string/array is the degenerate case: swap(lo, hi); lo++; hi--. Complexity: O(n) time, O(1) space.

Canonical problem: 3Sum (LeetCode 15) — sort, fix one, two-point the rest#

The dedup discipline is what interviewers watch. Sort, fix i, then run the opposite-ends scan on the suffix. Skip duplicates at every level.

Complexity: O(n²) time (outer fix × inner linear scan), O(1) extra beyond the output and the sort's O(log n) stack. The dedup trap: skipping duplicates only on the anchor i but not on lo/hi — or vice versa — produces duplicate triples like [-1,0,1] twice. You need all three skips. Do not dedup with a HashSet<List<Integer>>: it works but signals you didn't see the structure, and it's O(n) memory you didn't need. 4Sum generalizes: fix two, two-point the rest, O(n³).

Container With Most Water (LeetCode 11) & Trapping Rain Water (LeetCode 42)#

Both are greedy converging scans; the insight is which pointer to move.

Move-the-shorter-wall is provably optimal: area is bounded by the shorter wall, so moving the taller one can only shrink width without lifting the ceiling. For trap, when height[lo] < height[hi] we know some wall on the right is ≥ height[hi] > height[lo], so leftMax alone bounds the water above lo — no need to precompute both prefix maxima. Both O(n) time, O(1) space. (The prefix-max array version of trap is O(n) space — the two-pointer version is the senior answer.)

Valid Palindrome (LeetCode 125) & Dutch National Flag (LeetCode 75)#

lowercaseChar() is the Kotlin 1.5+ replacement for the deprecated toLowerCase() on Char; Java uses Character.toLowerCase(char). Sort Colors is Dijkstra's three-way partition — one pass, three pointers, O(1) space:

O(n) time, O(1) space. The trap: incrementing mid after a swap with high. You must re-examine the value that came from the unsorted right side, so leave mid put.

2. Two pointers — same direction (read / write)#

Recognition cue. Modify an array in place, remove/keep elements, compact, stable partition, "return the new length", or merge two sorted arrays without extra space. One pointer reads every element; the other writes only the survivors.

Template (slow-write / fast-read).

Remove Duplicates from Sorted Array (LC 26) & Merge Sorted Array (LC 88)#

Merge Sorted Array is the signature fill-from-the-back variant — writing forward would clobber unread nums1 values, so walk the write pointer down from the end:

Loop on j >= 0 only: if nums2 empties first, the rest of nums1 is already in place. All O(n) time, O(1) space. The trap: forgetting the i >= 0 guard, which underflows when nums2 holds the smallest elements.

3. Fast & slow pointers (Floyd's cycle detection)#

Recognition cue. Linked list or an implicit i → f(i) sequence: detect a cycle, find where it starts, find the middle, find a duplicate in O(1) space, is it a palindrome list. The tell is "O(1) extra space" on a structure you can only walk forward.

Node definitions (LeetCode's stubs name the field val; I use value in Kotlin to dodge the keyword clash, val in Java where it's legal):

Template: detect a cycle (LeetCode 141). fast laps slow inside any cycle, so they collide.

Find the cycle start (LeetCode 142) — and the math. Let a = distance head→entry, b = entry→meeting, L = cycle length. When they meet, slow walked a + b, fast walked a + b + kL (k full laps), and fast walked twice as far: 2(a+b) = a + b + kL ⇒ a + b = kL ⇒ a = kL − b = (k−1)L + (L − b). L − b is the distance from meeting point onward back to the entry. So a walker from head and a walker from the meeting point, each stepping once, both reach the entry after a steps. That's the whole reason the second loop works:

Find the Duplicate Number (LeetCode 287) — Floyd on value → index. With n+1 values in 1..n, the map i → nums[i] is a linked list with exactly one cycle whose entry is the duplicate (two indices point into it). This is the answer when the array must stay read-only and space must be O(1):

The other three, in Kotlin (Java is a mechanical translation of the same pointer moves):

All O(n) time, O(1) space. Traps: (1) the loop guard must be fast != null && fast.next != null or you NPE on even-length lists; (2) for cycle start, resetting slow (not fast) to head — both walk at speed 1 in phase two; (3) Happy Number relies on 1 → 1 being a fixed point so the fast pointer settles there.

4. Sliding window — fixed size k#

Recognition cue. "Subarray/substring of size exactly k", "window of k", moving average, find all anagrams / a permutation. The window width is pinned; you add one on the right and drop one on the left every step.

Template. Prime the first window, then slide: windowSum += in − out.

Note the Long accumulator — a size-k window of large ints overflows a 32-bit sum silently. This is the same overflow lesson as §7.

Canonical: Find All Anagrams (LeetCode 438) — a 26-bucket count window#

A fixed window plus a frequency vector: slide the window, compare counts in O(26) = O(1). Permutation in String (LC 567) is the boolean sibling (return true on the first match).

O(n · Σ) time with alphabet Σ = 26 (so O(n)), O(Σ) space. Traps: comparing counts before the window is full (i >= k - 1), and off-by-one on the start index i - k + 1.

5. Sliding window — variable size (grow / shrink) — THE template#

This is the single most important pattern in the guide; roughly a third of "medium" array/string problems reduce to it.

Recognition cue. Longest / shortest / max / min contiguous subarray or substring satisfying a constraint that is monotonic in width — "at most K …", "no repeats", "sum ≥ target", "contains all of T". Monotonic means: if a window is valid, every sub-window is valid too (for "at most" style), or if invalid, every super-window is invalid. That monotonicity is what lets left chase right without ever backing up.

The invariant, spoken aloud in the interview: "I expand right to include each new element. While the window violates the constraint, I contract left. When the loop settles, [left, right] is the best window ending at right, and I record the answer." Where you record depends on the goal:

Longest-valid template (record after restoring validity):

Shortest-valid template (record while valid, just before shrinking):

The only per-problem choices are: what state describes the window, what makes it invalid, and longest vs. shortest. Here are six instantiations.

5a. Longest Substring Without Repeating Characters (LC 3)#

State: a count map. Invalid when the just-added char appears twice.

Optimization worth naming: store each char's last index and jump left = max(left, lastIndex[c] + 1) — one move instead of a shrink loop. Correct either way at O(n); the jump version is where the "the left pointer can jump" trap lives (see §Problems).

5b–5d. At-most-K distinct, Longest Repeating Replacement, Min Subarray Sum#

characterReplacement has a famous subtlety: maxFreq is never decreased when shrinking. It's a high-water mark. That's fine — best only grows when a genuinely larger valid window appears, which requires a larger maxFreq; a stale maxFreq can never inflate the answer, it only lets the window glide at its current max width. minSubArrayLen requires non-negative numbers: the window sum must be monotonic in width for the shrink to be valid. With negatives, sliding window breaks and you switch to prefix + monotonic deque (or §7). Flag that assumption out loud.

5e. Minimum Window Substring (LC 76) — the hard canonical#

State: a need count of T, a window count, and a formed counter of how many distinct chars have met their required multiplicity. Shortest flavor.

The Integer == Integer trap is real and Java-specific: window.get(c) == need.get(c) autoboxes to reference comparison and silently breaks for counts above 127 (outside the Integer cache). Use .intValue() or .equals. See the companion guide's equals/hashCode section for why. All of §5: O(n) time (each index enters and leaves the window once), O(Σ) or O(k) space for the count map.

How this maps to your world: ONS's per-tenant webhook rate limiter is exactly this template on a time axis. A sliding-window-log limiter holds an ArrayDeque<Long> of send timestamps; on each event you add the new timestamp on the right and remove from the left every timestamp older than now − windowMillis, then reject if deque.size > limit. left chasing right = evicting expired timestamps. It's O(1) amortized per request and, unlike a fixed-bucket counter, has no boundary burst. The deque-of-timestamps is the window between two pointers.

6. The at-most-K → exactly-K trick, and counting subarrays#

Recognition cue. "Count subarrays with exactly K distinct / exactly S ones / exactly k odd numbers." Exactly-K resists a clean single window — and knowing why is the senior signal.

Why "exactly K" isn't a clean window. "At most K" is monotonic in width: shrink a valid window, it stays valid. So atMost(K) admits the grow/shrink template, and — the counting insight — a window [left, right] that is at-most-K contributes right − left + 1 subarrays ending at right (every start from left to right). Summing over right counts all at-most-K subarrays. "Exactly K" is not monotonic: shrinking an exactly-K window can drop you to K−1, so there's no clean "shrink while invalid" rule. The fix is subtraction:

exactly(K) = atMost(K) − atMost(K − 1)

Subarrays with K Different Integers (LC 992) & Binary Subarrays with Sum (LC 930)#

For 0/1 arrays the same subtraction counts sums, because window sum is monotonic:

Count Number of Nice Subarrays (LC 1248) — "exactly k odd numbers" — is this same code after mapping odd → 1, even → 0. All O(n) time, O(k) space. The alternative for these counting problems is prefix + hashmap (next section); the at-most trick is the tighter O(1)-space-ish option when values are non-negative/binary.

7. Prefix sums, difference arrays, prefix XOR#

Recognition cue. Many range-sum queries, "subarray summing to K" (esp. with negative numbers, where sliding window fails), submatrix sums, "apply many range updates then read", "subarray with XOR = k." Precompute cumulative aggregates once; answer each query in O(1).

1D prefix sum. Define P[0] = 0, P[i+1] = P[i] + nums[i], so sum(l..r) = P[r+1] − P[l]. The off-by-one is tamed by the n+1-length array with a leading zero.

Subarray Sum Equals K (LC 560) — prefix → count HashMap. sum(l..r) = k ⇔ P[r+1] − P[l] = k ⇔ P[l] = P[r+1] − k. Walk once, and for each running prefix count how many earlier prefixes equal prefix − k. Seed {0: 1} for subarrays that start at index 0. This handles negatives — the reason you can't use a sliding window here.

2D prefix sum, difference array, prefix XOR (Kotlin; each is a one-to-one Java port):

Complexity: 1D/XOR build O(n), query O(1); 2D build O(rows·cols), query O(1); difference array O(n + updates). The overflow trap dominates this section: a prefix sum of many ints overflows 32 bits silently and returns garbage — use long for the accumulator and the array. (XOR never overflows, so int is fine there.) The other trap: querying prefix − k after inserting the current prefix, which counts the empty subarray.

8. Cyclic sort#

Recognition cue. The values are a permutation of 1..n (or 0..n, or 0..n−1) — "find the missing / duplicated / smallest-missing-positive number," often with an O(1) extra space demand. Because each value has a known home index, you can sort in O(n) by swapping values into place, then scan for the slot that's wrong.

Template. Value v belongs at index v − 1 (for 1..n). Repeatedly swap the current value home until it's already there, then advance. Each swap places one value permanently, so it's O(n) total despite the nested-looking while.

First Missing Positive (LC 41) — the hard one, O(n) time & O(1) space. Ignore values outside 1..n; place each in-range v at index v − 1; then the first index whose value isn't i + 1 is the answer.

The 1..n sibling problems (Kotlin; scan after the same cyclic placement):

All O(n) time, O(1) space. For Find the Duplicate (LC 287), cyclic sort finds it (the value that's already home when its slot is taken is the duplicate) — but LC 287 forbids mutating the array, so the Floyd approach from §3 is the intended answer. Know both and state the constraint that picks one: cyclic sort mutates and needs a permutation-like domain; Floyd is read-only. The trap: writing while (i < n) with an i++ inside the swap branch — you must not advance i after a swap, because the value you just pulled in is unexamined.

Problems & how to solve them#

Problem: the window never shrinks (or shrinks forever). Root cause: the while condition tests the wrong polarity — you wrote "shrink while valid" for a longest problem, so it collapses every window, or "shrink while invalid" with a condition that's never true, so it grows unbounded and you get O(n²) or a wrong answer. Fix: pin the flavor first. Longest ⇒ while (invalid) shrink; record after. Shortest ⇒ while (valid) { record; shrink; }. Say the invariant out loud before coding it.

Problem: off-by-one on window length. Root cause: mixing inclusive/exclusive bounds — using right − left instead of right − left + 1, or comparing counts before the fixed window is full. Fix: fix a convention — [left, right] inclusive, width right − left + 1; a fixed window of size k is "full" when right ≥ k − 1. For prefix sums use the n+1 array with a leading zero so sum(l..r) = P[r+1] − P[l] needs no special-casing.

Problem: the answer is recorded at the wrong moment. Root cause: updating best inside the shrink loop for a longest problem (or after it for a shortest one). Fix: longest records after validity is restored (window is maximal-valid for this right); shortest records inside, right before removing nums[left] (window is minimal-valid). The two templates in §5 differ only here.

Problem: two pointers on unsorted input. Root cause: converging lo/hi on data that isn't sorted — the "move the smaller pointer" logic assumes monotonic sums and is meaningless otherwise; likewise sliding-window-sum assumes non-negative values. Fix: opposite-ends two pointers requires sorted or symmetric input — sort first (if indices don't matter) or switch to a HashMap (unsorted two-sum) / prefix-map (unsorted subarray-sum). Min-subarray-sum needs non-negative values; with negatives use prefix + deque.

Problem: 3Sum emits duplicate triples (the "duplicate explosion"). Root cause: skipping duplicates on only one of the three positions. Fix: skip the duplicate anchor (i > 0 && nums[i] == nums[i-1]) and skip duplicate lo/hi after recording a hit. All three, or you get repeats. A HashSet of triples masks the bug at O(n) memory cost — don't.

Problem: overflow in prefix sums / window sums. Root cause: accumulating many ints into a 32-bit int; it wraps silently and returns a plausible-looking wrong number. Fix: use long for any running sum over more than a handful of ints (prefix arrays, size-k window sums, running totals). XOR is safe in int. In Java, also avoid Integer == Integer for counts > 127 — compare .intValue().

Problem: forgetting the left pointer can jump. Root cause: in the last-index optimization for "longest without repeats," setting left = lastIndex[c] + 1 unconditionally lets left move backward when the duplicate is outside the current window, corrupting the width. Fix: left = maxOf(left, lastIndex[c] + 1) — the pointer may jump forward by many, but must never retreat. The shrink-loop version sidesteps this entirely.

Interview framing / how to sound senior#

• Lead with the recognition cue, not code. "'Longest contiguous substring with at most K distinct' — that's a monotonic-in-width predicate, so a grow/shrink window is O(n) time, O(K) space. Let me confirm the constraint direction, then write the template." You've named the pattern, the complexity, and the plan in one breath. Per the rubric research, senior scoring weights judgment and driving the session over raw speed — this is what that looks like.
• Always state time AND space, and the enabling assumption. "O(n) time because each index enters and leaves the window once; O(1) space because the count vector is fixed at 26. This assumes non-negative values so the window sum is monotonic — if negatives are possible I'd switch to prefix sums + a hashmap." Naming the assumption is a senior tell; it's the difference between a memorized template and understanding.
• Narrate the invariant as you code, then test it on a boundary. Empty input, single element, all-equal, all-distinct, the whole array being the answer, no answer existing. Interviewers score a distinct Testing axis; walking two adversarial cases (a negative number, a duplicate at the far end) catches the classic bugs above before they do.
• Call the trade-off, don't just pick. Sorted two-pointer 3Sum is O(n²)/O(1) and needs a sort; a hashmap variant avoids the sort but costs O(n) memory and messier dedup. Say which you're choosing and why. Reaching for HashSet to dedup 3Sum, or a prefix array where a two-pointer scan suffices, reads as "didn't see the structure."
• Know the version-dependent facts. Kotlin Char.lowercaseChar() (1.5+, replaced deprecated toLowerCase()); Java switch-arrow (14+/stable 17), List.of (9+), Map.merge/getOrDefault (8+). Say "Java 17" when you use an arrow switch.

Cheat-sheet#

Self-test#

1. State the two variable-window templates (longest vs. shortest) and the single line that differs between them.
2. Why must opposite-ends two pointers move the pointer at the smaller value in sorted two-sum? What breaks on unsorted input?
3. In 3Sum, exactly which three duplicate-skips are required, and what wrong output appears if you drop the lo/hi skips?
4. Derive a = (k−1)L + (L − b) for Floyd's cycle-start and explain why resetting one pointer to the head works.
5. Why does Find the Duplicate (LC 287) use Floyd rather than cyclic sort, given cyclic sort also finds it?
6. In Longest Repeating Character Replacement, why is it safe never to decrease maxFreq when the window shrinks?
7. Prove exactly(K) = atMost(K) − atMost(K−1) and explain why exactly-K has no clean single window.
8. When does Minimum Size Subarray Sum's sliding window fail, and what do you switch to?
9. Why does Subarray Sum Equals K use a prefix→count map instead of a sliding window? What seed does the map need and why?
10. Give two distinct places the integer-overflow / boxing trap bites in this guide and the fix for each.
11. Sort Colors: after swapping nums[mid] with nums[high], why must you not advance mid?
12. Merge Sorted Array in place: why fill from the back, and why is the loop condition j >= 0?
13. First Missing Positive: why is it O(n) despite the nested while, and why must i not advance after a swap?
14. For the last-index optimization in Longest Substring Without Repeating Characters, why is left = max(left, last[c]+1) — not last[c]+1 — mandatory?

Lineage / sources#

The three-way partition is Dijkstra's Dutch National Flag (1976). Cycle detection is Floyd's tortoise-and-hare; Brent's variant is a faster cousin worth naming. The pattern taxonomy and names (fast/slow, sliding window, cyclic sort, at-most-K) follow Grokking the Coding Interview (DesignGurus/Educative) and NeetCode 150; the "14 patterns" framing is Fahim ul Haq's widely-reposted list. Problem numbers reference LeetCode (3, 11, 15, 26, 41, 42, 75, 76, 88, 125, 141, 142, 167, 202, 209, 234, 268, 287, 303, 304, 340, 370, 424, 438, 448, 560, 567, 876, 904, 930, 992, 1248, 1310). Interview-format and rubric notes (round mix by level, the four scoring axes, the practical/"simulate a stream" tilt at infra shops like Snowflake) come from Tech Interview Handbook, interviewing.io's 100K-interview study, and the 2025-26 vendor guides synthesized in the series playbook (00). Treat exact round counts as typical-not-guaranteed. For the internals of any structure used here as a tool — HashMap, ArrayDeque, PriorityQueue — see the companion data-structures-java-kotlin-study-guide.md.