The Sliding Window Pattern: Fixed vs Dynamic Windows
Master the sliding window pattern. Contrast Fixed-Size windows (maximum sum subarray of size K) with Dynamic-Size windows (longest substring without repeating characters).
By the end, you’ll be able to…
- Implement Fixed-Size Sliding Windows in O(N) time by adding the incoming element and subtracting the outgoing element.
- Implement Dynamic-Size Sliding Windows with expand/shrink pointer mechanics.
- Apply character frequency maps to solve string permutation and substring problems.
01Fixed-Size vs Dynamic Sliding Windows
The Sliding Window pattern is applied to array or string problems that search for optimal contiguous subarrays. Instead of recalculating properties of the subarray from scratch in O(K) time for every starting position (totaling O(N * K)), the sliding window maintains running state in O(1) amortized time per step.
Fixed-Size Windows maintain an invariant window width K. At each step, the window slides one position right: we add the contribution of the new incoming element at the right, and subtract the contribution of the exiting element at the left. Dynamic-Size Windows expand the right pointer to satisfy a condition, and contract the left pointer when a constraint is violated.
02Dynamic Window: Longest Substring Without Repeating Characters
In this classic problem, we find the length of the longest substring without repeating characters. A naive check of all substrings takes O(N^3) time.
Using a dynamic sliding window with an integer array map of last seen character indices, we expand the right pointer one character at a time. If we encounter a duplicate character, we immediately slide the left pointer to lastSeen[char] + 1, skipping all redundant checks in O(N) total time.
03Dry-Run Trace Table for Longest Unique Substring
Let us trace the dynamic window algorithm on the string s = "pwwkew":
Notice how at step 3, when 'w' is repeated, the left pointer jumps directly to index 2, maintaining a valid unique window at all times.
+------+-------+-------+------+------------+------------------+----------+| Step | Right | Char | Left | Window Str | Action | MaxLen |+------+-------+-------+------+------------+------------------+----------+| 1 | 0 | 'p' | 0 | "p" | lastIndex['p']=0 | 1 || 2 | 1 | 'w' | 0 | "pw" | lastIndex['w']=1 | 2 || 3 | 2 | 'w' | 2 | "w" | Jump left to 1+1 | 2 || 4 | 3 | 'k' | 2 | "wk" | lastIndex['k']=3 | 2 || 5 | 4 | 'e' | 2 | "wke" | lastIndex['e']=4 | 3 (NEW!) || 6 | 5 | 'w' | 3 | "kew" | Jump left to 2+1 | 3 |+------+-------+-------+------+------------+------------------+----------+Maximum Window Length: 3 ("wke" or "kew")!04Why This Matters in Production
Sliding window algorithms power real-time rate limiters (such as Sliding Window Log algorithms in API Gateways), network packet congestion control (TCP Sliding Window Protocol), and live financial volatility metrics.
By updating running statistics in constant O(1) time per event, server instances process millions of incoming streaming requests per second without accumulating memory buffers or performing full collection scans.
05Production Architecture & Engineering Trade-Offs
In large-scale enterprise codebases, rigorous domain modeling relies on enforcing structural invariants at the type level rather than relying on defensive runtime validation. Modern Java leverages sealed types and records to turn runtime type errors into compile-time exhaustiveness guarantees. When designing domain transfer objects or persistent entities, ensuring immutability protects against unintended side effects across concurrent worker threads.
Furthermore, avoiding deep inheritance hierarchies in favor of composition and interface contracts eliminates fragile base class anti-patterns. By encapsulating state mutations within well-defined service boundaries and exposing pure functional transformers, software architects build maintainable, audit-compliant systems that scale smoothly across distributed cloud infrastructure.
The ideas worth keeping.
- Fixed-size windows update metrics in O(1) time by adding the incoming and subtracting the exiting element.
- Dynamic windows expand right to satisfy constraints and shrink left when constraints are broken.
- Both pointers move strictly forward, guaranteeing linear O(N) overall execution time.
Make it yours.
Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.
Exercise 1: Minimum Size Subarray Sum
Write an algorithm minSubArrayLen(int target, int[] nums) that returns the minimum length of a contiguous subarray whose sum is >= target in O(N) time.
Explore a worked solution
public int minSubArrayLen(int target, int[] nums) { int left = 0, sum = 0, minLen = Integer.MAX_VALUE; for (int right = 0; right < nums.length; right++) { sum += nums[right]; while (sum >= target) { minLen = Math.min(minLen, right - left + 1); sum -= nums[left++]; } } return minLen == Integer.MAX_VALUE ? 0 : minLen;}Expanding right adds elements; while condition is met, contracting left shrinks the window to find minimal length.
Exercise 2: String Permutation Anagram Search
Explain how a fixed sliding window of size M with a frequency count array of size 26 identifies all anagram starting indices of string P in string S in O(N) time.
Explore a worked solution
Maintain counts of P. Slide window of length P.length over S. Maintain matches count (0..26). When incoming/outgoing char counts match P, record index.Sliding window updates character delta counts in O(1) time, verifying permutations without re-sorting strings.
What stayed with you?
Check the ideas while they’re fresh. Your answers stay in this page and feedback appears as you go.
Exercise 1: Minimum Size Subarray Sum
Write an algorithm minSubArrayLen(int target, int[] nums) that returns the minimum length of a contiguous subarray whose sum is >= target in O(N) time.
Build successful. (Java 15) [Process exited normally]
Keep exploring.
The official references behind this lesson, when you want a second angle or the full details.
One lesson closer.
Reading is a start. Trying it yourself makes the connection.