Week 2
Two Pointers & Sliding Window
Walk through an array or string with two fingers instead of one, and turn many slow "check every pair" problems into a single fast pass.
- Converging two pointers
- Sort first, then two pointers
- Greedy pointer move
- Track the best so far in one pass
- Variable-size sliding window
- Window with counts and a validity check
- Fixed-size sliding window
Last week you met arrays and hash maps. This week is about how you walk through an array. Most of these problems have an obvious answer that checks every pair of items, which is slow. The trick, again and again, is to keep two positions in the array and move them cleverly, so that one pass is enough.
An array is a row of boxes, and each box has an index: its position, counting from 0. A pointer is just a variable that holds an index. It “points at” one box.
- 10
- 31
- 42
- 63
- 84
What you can do with a pointer, and what it costs:
- Read the value it points at:
nums[left]. One step, however long the array. - Move it one box:
left++(JavaScript) orleft += 1(Python). One step. - Compare two pointers:
left < rightasks “is left still to the left of right?”. One step.
const nums = [1, 3, 4, 6, 8];let left = 0; // a pointer is just a numberlet right = nums.length - 1; // the last index is length - 1, here 4console.log(nums[left], nums[right]); // 1 8left++; // move one step rightright--; // move one step leftconsole.log(left < right); // true: they haven't met yetnums = [1, 3, 4, 6, 8]left = 0 # a pointer is just a numberright = len(nums) - 1 # the last index is length - 1, here 4print(nums[left], nums[right]) # 1 8left += 1 # move one step rightright -= 1 # move one step leftprint(left < right) # True: they haven't met yetBig-O describes how the work grows as the input grows. Checking every pair of
n items is about n × n ÷ 2 checks: O(n²),
so doubling the input makes four times the work.
With two pointers, each pointer only moves forward (or only inward), and
never more than n times. So even if there’s a loop inside a loop, the total
number of moves is at most about 2n: O(n).
Double the input, double the work. For 100,000 items that’s ~200,000 steps instead of ~5 billion.
A string is a piece of text, like "hello". For our purposes it’s an array:
each character (letter, digit, space or symbol) sits in a box with an index.
- h0
- e1
- l2
- l3
- o4
A substring is a run of characters that sit next to each other: "ell"
is a substring of "hello", but "hlo" is not. The same idea for arrays is
called a subarray. You’ll also see the word contiguous, which just means
“next to each other, no gaps”.
const s = "hello";s.length; // 5s[1]; // "e"s.slice(1, 4); // "ell" (from index 1 up to, not including, 4)s[0].toLowerCase() === "h"; // compare letters ignoring cases.charCodeAt(0) - "a".charCodeAt(0); // 7: "h" is letter number 7 (a = 0)s = "hello"len(s) # 5s[1] # "e"s[1:4] # "ell" (from index 1 up to, not including, 4)s[0].lower() == "h" # compare letters ignoring caseord(s[0]) - ord("a") # 7: "h" is letter number 7 (a = 0)One thing to know: in both languages strings can’t be changed in place.
s.slice(...), s[1:4] and s + "!" all build a new string, which costs
time and memory proportional to its length. Two pointers let us look at a
string without copying it.
A window is the stretch of an array or string between two pointers, left
and right, both included. Its length is right − left + 1 (from index 2 to
index 4 is 3 items, not 2).
- a0
- b1
- c2
- a3
- b4
Sliding a window means: add the item that enters on the right, remove the item that leaves on the left, and keep a running summary (a sum, a set, some counts) up to date. Each update is one step, instead of re-reading the whole window.
What it is. Put one pointer at each end of the array and move them
toward each other until they meet. At every step you look at the pair
(arr[left], arr[right]) and decide which pointer to move (or both). The pointers
only ever move inward, so it’s one pass.
Pattern
Converging two pointers
Use it when: you compare or pair up items from both ends: checking symmetry, or finding a pair in a sorted array.
Signal words
- “palindrome”
- “sorted array”
- “pair that sums to”
- “reverse in place”
- “O(1) extra space”
Template: converging two pointers
function converge(arr) { let left = 0; let right = arr.length - 1; while (left < right) { // 1. look at arr[left] and arr[right] // 2. if this pair is the answer (or proves there's none), return // 3. otherwise move one pointer inward (or both): if (shouldMoveLeft(arr[left], arr[right])) { left++; } else { right--; } } return null; // the pointers met}def converge(arr): left, right = 0, len(arr) - 1 while left < right: # 1. look at arr[left] and arr[right] # 2. if this pair is the answer (or proves there's none), return # 3. otherwise move one pointer inward (or both): if should_move_left(arr[left], arr[right]): left += 1 else: right -= 1 return None # the pointers met- r0
- a1
- c2
- e3
- c4
- a5
- r6
Problems this week: Valid Palindrome, Two Sum II, Container With Most Water, and the inner loop of 3Sum.
What it is. Many problems don’t care about the order of the input, only about which values go together. Then you’re free to sort first. A sorted array lets converging pointers make smart moves (too small? go right; too big? go left), and it puts equal values next to each other, so skipping duplicates is just “is this the same as the one before?”.
Pattern
Sort first, then two pointers
Use it when: the answer is a set of values (not positions), you need pairs or triplets with a target sum, and duplicates must be listed only once.
Signal words
- “triplets”
- “sum to zero”
- “unique combinations”
- “no duplicates”
- “return the values”
Template: sort, fix one, two pointers, skip duplicates
nums.sort((a, b) => a - b); // numbers, not text!for (let i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] === nums[i - 1]) continue; // same as before: skip let left = i + 1; let right = nums.length - 1; while (left < right) { const sum = nums[i] + nums[left] + nums[right]; if (sum < target) left++; else if (sum > target) right--; else { save(nums[i], nums[left], nums[right]); left++; right--; while (left < right && nums[left] === nums[left - 1]) left++; // skip repeats } }}nums.sort()for i in range(len(nums) - 2): if i > 0 and nums[i] == nums[i - 1]: continue # same as before: skip left, right = i + 1, len(nums) - 1 while left < right: total = nums[i] + nums[left] + nums[right] if total < target: left += 1 elif total > target: right -= 1 else: save(nums[i], nums[left], nums[right]) left += 1 right -= 1 while left < right and nums[left] == nums[left - 1]: left += 1 # skip repeats- -40
- -11
- -12
- 03
- 14
- 25
Problems this week: 3Sum. Two Sum II is the same idea with the sorting already done for you.
What it is. A greedy choice is one that takes the best-looking option right now, without trying every possibility. In this pattern, two pointers start at both ends and at each step you move the side that limits you, because you can prove the other side can’t do better. Each move rules out one item for good.
Pattern
Greedy pointer move
Use it when: the value of a pair is capped by the smaller (or worse) of the two sides, so keeping the worse side and moving the better one can never help.
Signal words
- “maximum area”
- “container”
- “width × height”
- “move the shorter side”
- “best pair”
Template: measure, then move the limiting side
let left = 0;let right = arr.length - 1;let best = 0;while (left < right) { best = Math.max(best, score(left, right)); // measure this pair if (arr[left] < arr[right]) left++; // left is the limit: drop it else right--; // right is the limit (or a tie)}return best;left, right = 0, len(arr) - 1best = 0while left < right: best = max(best, score(left, right)) # measure this pair if arr[left] < arr[right]: left += 1 # left is the limit: drop it else: right -= 1 # right is the limit (or a tie)return bestProblems this week: Container With Most Water.
What it is. Walk through the array once, keeping a small summary of everything before the current item (like the smallest value so far) and the best answer so far. At each item, combine it with the summary to get a candidate answer. You never look back, because the summary already remembers what mattered.
Pattern
Track the best so far in one pass
Use it when: each position's answer depends only on a simple summary of what came before it (minimum, maximum, sum).
Signal words
- “buy then sell”
- “maximum difference”
- “later minus earlier”
- “max profit”
- “single pass”
Template: summary so far + best so far
let lowest = Infinity; // summary of everything beforelet best = 0; // best answer so farfor (const x of arr) { if (x < lowest) { lowest = x; // update the summary } else { best = Math.max(best, x - lowest); // use the summary }}return best;lowest = float("inf") # summary of everything beforebest = 0 # best answer so farfor x in arr: if x < lowest: lowest = x # update the summary else: best = max(best, x - lowest) # use the summaryreturn bestProblems this week: Best Time to Buy and Sell Stock.
What it is. Keep a window [left, right] that always obeys some rule (for
example, “no repeated characters”). Move right forward one item at a time to
grow the window. If the new item breaks the rule, move left forward to
shrink it until the rule holds again. After each step, the window is valid, so
record its length.
Pattern
Variable-size sliding window
Use it when: you want the longest (or shortest) contiguous stretch that obeys a rule, where adding items can only break the rule and removing them can only fix it.
Signal words
- “longest substring”
- “contiguous subarray”
- “without repeating”
- “at most”
- “smallest window”
Template: grow right, shrink left while invalid
let left = 0;let best = 0;for (let right = 0; right < s.length; right++) { add(s[right]); // grow: s[right] enters while (!windowIsValid()) { remove(s[left]); // shrink: s[left] leaves left++; } best = Math.max(best, right - left + 1); // the window is valid here}return best;left = 0best = 0for right in range(len(s)): add(s[right]) # grow: s[right] enters while not window_is_valid(): remove(s[left]) # shrink: s[left] leaves left += 1 best = max(best, right - left + 1) # the window is valid herereturn best- a0
- b1
- c2
- a3
- b4
- a0
- b1
- c2
- a3
- b4
Problems this week: Longest Substring Without Repeating Characters, and Longest Repeating Character Replacement (with counts, next pattern).
What it is. The same grow-and-shrink window, but the rule depends on how many of each item are inside. Keep a count map (item → how many times it’s in the window): add 1 when an item enters, subtract 1 when it leaves. The validity check is a small formula on those counts, such as “length − (count of the most common letter) ≤ k”.
Pattern
Window with counts and a validity check
Use it when: whether a window is allowed depends on how many of each item it holds, and you want the longest allowed window.
Signal words
- “replace at most k”
- “at most k distinct”
- “same letter after changes”
- “longest substring with”
- “frequency”
Template: window + count map + validity check
const count = new Map(); // item -> how many times it's in the windowlet left = 0;let best = 0;for (let right = 0; right < s.length; right++) { count.set(s[right], (count.get(s[right]) ?? 0) + 1); while (!isValid(count, right - left + 1)) { count.set(s[left], count.get(s[left]) - 1); left++; } best = Math.max(best, right - left + 1);}return best;count = {} # item -> how many times it's in the windowleft = 0best = 0for right in range(len(s)): count[s[right]] = count.get(s[right], 0) + 1 while not is_valid(count, right - left + 1): count[s[left]] -= 1 left += 1 best = max(best, right - left + 1)return best- A0
- A1
- B2
- A3
- B4
change 1 ≤ k = 1: valid
Problems this week: Longest Repeating Character Replacement.
What it is. Sometimes the window size is fixed: exactly k items (often
k is the length of another string). Build the summary for the first k items,
then slide: one item enters on the right, one leaves on the left, and the
size never changes. Often the summary is a frequency count, and the question is
“does this window have the same counts as a target?” (that’s frequency matching).
Pattern
Fixed-size sliding window
Use it when: the problem is about blocks of exactly k neighbouring items, such as finding an anagram or permutation of one string inside another.
Signal words
- “permutation of s1 in s2”
- “anagram substring”
- “window of size k”
- “every k consecutive”
- “same letter counts”
Template: build the first window, then slide
// k = window size, e.g. s1.lengthfor (let i = 0; i < k; i++) add(s[i]); // the first windowif (matches()) return true;for (let right = k; right < s.length; right++) { add(s[right]); // enters on the right remove(s[right - k]); // leaves on the left if (matches()) return true;}return false;# k = window size, e.g. len(s1)for i in range(k): add(s[i]) # the first windowif matches(): return Truefor right in range(k, len(s)): add(s[right]) # enters on the right remove(s[right - k]) # leaves on the left if matches(): return Truereturn False- e0
- i1
- d2
- b3
- a4
- o5
- o6
- o7
| a | b | d | |
|---|---|---|---|
| need (s1) | 1 | 1 | 0 |
| have (window) | 0 | 1 | 1 |
Problems this week: Permutation in String.
Both use two indexes, so they’re easy to mix up. The difference is what you care about:
- Two pointers care about two items (a pair, or the two ends). What’s in between doesn’t matter.
- A sliding window cares about everything between the pointers: the whole stretch, its length, its contents.
A quick checklist, in order:
- Is it about a contiguous stretch (substring, subarray, “consecutive”)?
→ Sliding window.
- Is the length given (k, or the length of another string)? → Fixed-size window.
- Are you looking for the longest or shortest stretch that obeys a rule? → Variable-size window.
- Does the rule depend on how many of each item are inside? → add a count map.
- Is it about a pair (or triplet) of items, and the stuff between them doesn’t
count? → Two pointers.
- Is the array sorted, or can you sort it without losing what you need? → Converging pointers (sort first if needed).
- Is each pair’s value capped by its weaker side? → Greedy pointer move.
- Is it “best later item minus earlier item”? → Track the best so far (a pointer and a running summary).
- Does the problem need original indexes from unsorted input? → Probably not this week’s tools: use a hash map (week 1).
Solve them in this order. Each one adds one new idea on top of the last:
- Valid Palindrome (Easy): the purest form of converging pointers. Only one new thing to learn: two indexes moving inward.
- Two Sum II: the pointers now decide which way to move, using the sum and the sorted order. Compare it with week 1’s hash-map Two Sum.
- 3Sum: wrap Two Sum II in a loop, and learn sorting first and skipping duplicates.
- Container With Most Water: the move is no longer about a sum but a greedy argument. Practise explaining why it’s safe.
- Best Time to Buy and Sell Stock (Easy): a gentle bridge from pointers to windows. One pass, a running minimum, a best-so-far.
- Longest Substring Without Repeating Characters: your first real sliding window. Grow right, shrink left, using a set.
- Longest Repeating Character Replacement: the same window with counts and a formula for “valid”. The trickiest idea of the week; take it slowly.
- Permutation in String: a fixed-size window with letter counts. A good final check that you can build the counts, slide, and compare.
If you get stuck on one, go back to the pattern section above, read the template, and play the visualizer on the problem page step by step before writing code.
This week's problems
0 of 8 done
Decide whether a sentence reads the same forwards and backwards once you ignore spaces, punctuation and capital letters.
In a sorted list, find the two numbers that add up to a target, using only a fixed amount of extra memory.
Pick two walls that, together with the ground, hold the most water, without measuring every pair.
Find every different group of three numbers that adds up to zero, without listing the same group twice.
Given a stock's price for each day, find the biggest profit from buying once and selling once later.
Find the length of the longest stretch of a string in which no character appears twice.
Change at most k letters so that the longest possible run of one repeated letter appears, and return that run's length.
Check whether some rearrangement of a short string appears as a block of neighbouring letters inside a longer string.