Sliding window + week 3 wrap

If you only learn one DSA pattern this week, learn sliding window. It solves more leetcode-medium problems than any other single technique, and the shape is small enough to memorise once and reach for forever.

The setup — you have an array (or string) and you want the best subrange satisfying some constraint. Best could be longest, shortest, count of, max sum, anything. The brute force is O(n²) — enumerate all subranges, check each.

The sliding window upgrade — keep two pointers, left and right, defining the current window. Expand from the right; shrink from the left when the window violates the constraint. Track the optimum window seen as you go.

Key property — each element enters the window once (when right passes it) and leaves at most once (when left passes it). Total work — O(n).

When does sliding window apply? Three signals.

One — the goal is about a subarray or substring. 'Longest', 'shortest', 'count of', 'minimum window containing', etc.

Two — the constraint is monotonic in window size. Adding to the window can only make the constraint 'better' or 'worse' in one direction. (Sum strictly grows when you add positive numbers; the count of distinct chars can only grow.)

Three — each element is involved at most twice (entering, leaving). If you'd need to revisit elements multiple times, sliding window probably isn't the right tool.

Variants.

Fixed-size window. The window is exactly k wide; slide step by step. Useful for 'max sum of k consecutive elements'.

Variable window. Grow and shrink based on the constraint. Useful for 'longest substring with at most k distinct chars'.

The distinction matters because the loop structure differs slightly. Fixed-size — single for-loop, with the right edge auto-derived from left. Variable — while-loop or for-with-inner-while, expanding and shrinking.

Memorise the shapes; the variants are tweaks.

The skill that separates 'I solve sliding-window problems when told it's sliding window' from 'I see a problem and recognise it's sliding window' is pattern recognition. Three signals that, when all three are present, mean the answer is almost certainly a sliding window.

Signal one — the goal involves a subarray or substring. 'Longest', 'shortest', 'count of', 'maximum', 'minimum window containing'. Anything where the answer is itself a contiguous range of the input.

Signal two — the constraint is monotonic with window size. As the window grows, the constraint either keeps getting 'worse' (e.g., sum exceeds target) or keeps getting 'better' (e.g., count of distinct elements grows). Critically, growing or shrinking doesn't 'flip' the constraint unpredictably.

Signal three — each element should logically enter and leave the window at most once. If your problem requires re-examining the same element after it leaves, sliding window is wrong.

If all three signals fire, sliding window is your tool. Code the shape (left, right, expand-shrink, track optimum), specialise the constraint check, done.

If signals don't fire, consider:

Hash map for one-pass lookup. (Two-sum on unsorted, subarray-sum-equals-K with prefix.)

Prefix sum for range queries. (Multiple sum-in-range queries on a static array.)

Dynamic programming for overlapping subproblems. (Longest common subsequence, edit distance.)

Binary search for monotonic answer space. (Min capacity to ship in D days.)

Backtracking for combinatorial enumeration. (All subsets, permutations, valid configurations.)

A practical exercise — pick five leetcode-medium problems labelled 'sliding window'. Try to articulate the three signals for each before solving. The articulation IS the skill; the code falls out once you've named the pattern.

Given an array of POSITIVE integers and a target, find the shortest contiguous subarray whose sum is at least the target. Return its length, or 0 if no such subarray exists.

This is sliding window in its purest form. All three signals fire — subarray goal (shortest), monotonic constraint (sum grows when you add a positive, shrinks when you remove), each element handled at most twice.

Look at the snippet.

We initialise left=0, total=0, best=infinity.

For each right, x in enumerate(nums) — we expand the window by adding x to total.

Then, while total >= target — the window is valid. Try to shrink from the left while keeping it valid. Update best with the current length. Subtract nums[left] from total. Increment left.

The inner while-loop is the shrink phase. It continues to shrink as long as the window remains valid (sum >= target). When it stops, the window is JUST below the constraint — we've found the smallest valid window ending at this right.

The outer for-loop expands the right edge.

Return — 0 if best is still infinity (no valid window found), else best.

Key complexity argument — left and right each move at most n times across the entire algorithm. left can only go forward (never backward). Total work — O(n).

The shape — for-with-inner-while — is the standard variable-window template. Memorise it. Variants include longest-substring-without-repeats (similar shape, different shrink condition), minimum-window-substring (more complex constraint check), longest-substring-with-at-most-k-distinct (count-based constraint).

One pass. O(n). Each element joins and leaves at most once. The pattern is so consistent that once you've coded three of these, you can write a fourth from scratch.

End-of-week-three reflection. If you've followed along but haven't actually written code, you'll forget most of what we covered. The cure is targeted practice on the highest-leverage problems.

Five problems that, between them, cover the patterns from this week and the most common interview shapes. Solve them in this order; understand each before moving on.

One. Two-sum (Leetcode #1). Hash map for O(n). The canonical 'trade memory for time' answer.

Two. Longest substring without repeating characters (Leetcode #3). Sliding window with a hash map of seen positions. Cleanest example of the variable-window pattern.

Three. Valid parentheses (Leetcode #20). Stack pattern in its simplest form. Push openers, pop and check on closers, end with empty stack.

Four. Reverse linked list (Leetcode #206). Three-pointer dance. Tests pointer manipulation, the foundational skill behind tree and graph problems.

Five. Number of islands (Leetcode #200). BFS or DFS on a grid. Tests adapting the BFS template to a non-obvious neighbours function.

These five cover hash map, sliding window, stack, pointer manipulation, BFS — the 'big five' DSA patterns by frequency. About 80% of leetcode-medium problems are variations on these.

My recommendation — solve each, then explain it out loud (literally, talking) as if to an interviewer. The talking-through is where you discover what you understand vs what you memorised. If you can't explain why two-sum works in O(n), code without notes, you don't understand it yet.

After these five, if interviews are your goal, knock out 25-50 more leetcode mediums. The patterns repeat; recognising them is the skill.

End of week three. 21 days. 105 posts. We're 23% of the way through the sprint.

DSA week one is in the books. Tomorrow week 4 begins with recursion and goes through binary search, sorting, trees, graphs, and dynamic programming. The hard half of DSA.

What we covered this week.

Big-O as a label, not math. Six classes (constant, log, linear, linearithmic, quadratic, exponential). 30-second estimation recipe. Profile before optimising.

Arrays — list as dynamic array, asymmetric ops, two-pointer in three flavours, prefix sums for O(1) range queries.

Strings — immutable, code-point indexed, build with join, character counting via Counter, sliding window for substring problems, str.translate over regex for char swaps.

Linked lists — exist for O(1) insert/delete given a pointer, three-pointer reverse dance, Floyd's slow/fast cycle detection, and the honest 'you'll mostly see them in interviews, not real code'.

Hash maps and sets — drop a Big-O class for free, defaultdict for group-by, two-sum in one pass, set operators (& | - ^) for collection comparison.

Stacks and queues — pick by access pattern (LIFO vs FIFO), parentheses pattern (push openers, pop on closers), BFS template, deque-not-list for queues.

Sliding window — three signals (subarray goal, monotonic constraint, each element in/out once), variable-window template (for-with-inner-while), the pattern that solves most 'best subrange' problems.

Five problems to lock the patterns — two-sum, longest unique substring, valid parentheses, reverse linked list, num-islands.

Next week. Recursion as a thinking tool. Binary search beyond find-an-element. Why Python uses timsort. Trees and BFS/DFS in depth. Graphs. DP without the fear.

Thank you for showing up this week. See you tomorrow.