Fixed Window Rate Limiter Bug — 2x Burst at Boundaries

Subarray and substring problems dominate coding interviews and production systems alike. Finding the maximum sum of k consecutive elements, detecting rate limit violations in a time window, or identifying the longest substring without repeating characters — all of these share the same structure: a contiguous window of data that must be evaluated efficiently.

The naive approach checks every possible window from scratch — O(n²) or worse. Sliding window eliminates this by maintaining the window state incrementally. When the window slides one position to the right, you add the new element and remove the old one in O(1), rather than recomputing the entire window. This single insight converts O(n*k) brute force into O(n) single-pass.

Two flavors exist: fixed-size windows (constant k) and variable-size windows (expand/contract based on a constraint). Both share the invariant that each element enters and exits the window at most once. Recognizing which flavor applies — and correctly implementing the constraint logic — is the difference between a correct solution and a silent wrong answer.

Why Fixed Window Rate Limiting Leaks 2x Traffic at Boundaries

The sliding window technique solves a specific failure: fixed window rate limiters allow up to 2x burst traffic at window boundaries. A fixed window resets counters at rigid intervals (e.g., every second), so a client can send N requests at 0:00.999 and another N at 0:01.001 — effectively doubling throughput in a 2ms span. Sliding window replaces the hard reset with a continuous, rolling time frame, typically implemented via a sorted log of timestamps or a sliding counter that weights partial windows.

In practice, sliding window uses O(n) memory per key (timestamp log) or O(1) with a hybrid approach: track the current window count and the previous window's count, then interpolate. The formula is: weight = (current_time - window_start) / window_size; estimated_count = previous_count * (1 - weight) + current_count. This gives sub-second granularity without per-request storage. The tradeoff is slight approximation — exact sliding windows require full logs, but most production systems accept <5% error for constant memory.

Use sliding window wherever burst tolerance must be bounded: API rate limiting, login throttling, or any resource where fixed windows cause predictable abuse. It’s the standard for production gateways (Kong, Envoy) because it prevents the “midnight madness” pattern — clients learning to hammer exactly at reset boundaries. Without it, your rate limiter is a sieve.

Worked Example — Maximum Sum Subarray of Size K

Find the maximum sum subarray of size k=3 in arr=[2,1,5,1,3,2].

1. Initialize: window_sum = sum(arr[0..2]) = 2+1+5 = 8. max_sum = 8.
2. Slide right: i=3. Remove arr[0]=2, add arr[3]=1. window_sum = 8 - 2 + 1 = 7. max_sum stays 8.
3. i=4: remove arr[1]=1, add arr[4]=3. window_sum = 7 - 1 + 3 = 9. max_sum = 9.
4. i=5: remove arr[2]=5, add arr[5]=2. window_sum = 9 - 5 + 2 = 6. max_sum stays 9.
5. Result: 9 (subarray [5,1,3]).

For variable-size windows (e.g., longest substring with at most k distinct chars): expand right pointer, and when the constraint is violated, shrink by advancing the left pointer until valid again. The window always contains a valid subarray. Each element enters and leaves the window at most once, giving O(n) time.

package io.thecodeforge.algo;

public class MaxSumSubarrayFixedWindow {

    /**
     * Finds the maximum sum of any contiguous subarray of size k.
     * Fixed-size sliding window — O(n) time, O(1) space.
     */
    public static int maxSumSubarray(int[] arr, int k) {
        if (arr.length < k) {
            throw new IllegalArgumentException("Array length must be >= k");
        }

        // Compute sum of first window
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        int maxSum = windowSum;

        // Slide the window: add right element, remove left element
        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i];      // add incoming element at right edge
            windowSum -= arr[i - k];  // remove outgoing element at left edge
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 1, 3, 2};

        System.out.println("Max sum (k=3): " + maxSumSubarray(arr, 3));  // 9 — [5,1,3]
        System.out.println("Max sum (k=2): " + maxSumSubarray(arr, 2));  // 6 — [5,1]
        System.out.println("Max sum (k=4): " + maxSumSubarray(arr, 4));  // 10 — [5,1,3,2]

        // Trace the window slides for k=3:
        // [2,1,5] sum=8  max=8
        // [1,5,1] sum=7  max=8  (removed 2, added 1)
        // [5,1,3] sum=9  max=9  (removed 1, added 3)
        // [1,3,2] sum=6  max=9  (removed 5, added 2)
    }
}

How Sliding Window Works — Plain English and Step-by-Step

A sliding window maintains a contiguous subarray or substring and slides it across the input to avoid O(n^2) brute force.

Fixed-size window (size k) — max sum subarray: 1. Compute sum of first k elements. 2. For each new position i from k to n-1: add arr[i], subtract arr[i-k]. Update max. O(n) total — each element is added and removed exactly once.

Variable-size window — longest substring without repeating characters: 1. Use left and right pointers, both starting at 0. Maintain a seen dict of last index. 2. Expand right: for each char, if it was seen at index >= left, move left to seen[char]+1. 3. Update seen[char] = right. Record window length right-left+1 if it's a new maximum.

Worked example — fixed window k=3, arr=[2,1,5,1,3,2], find max sum: Window [2,1,5]: sum=8, max=8. Slide: -2+1=7. Window [1,5,1]: sum=7. max=8. Slide: -1+3=9. Window [5,1,3]: sum=9. max=9. Slide: -5+2=6. Window [1,3,2]: sum=6. max=9. Answer: 9.

package io.thecodeforge.algo;

/**
 * Summary of the two sliding window flavors.
 * Both achieve O(n) by visiting each element at most twice.
 */
public class SlidingWindowPatternSummary {

    /*
     * FIXED-SIZE WINDOW
     * ─────────────────
     * Setup: compute sum/state of first k elements.
     * Slide: add arr[right], subtract arr[right-k]. Update result.
     * Constraint: window size is always exactly k.
     * Time: O(n), Space: O(1)
     * Examples: max sum subarray of size k, moving average, max of all subarrays of size k.
     */

    /*
     * VARIABLE-SIZE WINDOW
     * ────────────────────
     * Setup: left=0, right=0, empty state.
     * Expand: advance right, add arr[right] to state.
     * Shrink: while constraint violated, remove arr[left], advance left.
     * Constraint: dynamically maintained (distinct count, sum threshold, etc.)
     * Time: O(n), Space: O(k) where k is constraint size
     * Examples: longest substring without repeating, min window substring, longest subarray with sum <= target.
     */

    public static void main(String[] args) {
        System.out.println("Sliding Window Flavors:");
        System.out.println("1. Fixed-size   — window is always k elements. Add right, subtract left.");
        System.out.println("2. Variable-size — expand right, shrink left when constraint violated.");
        System.out.println("\nBoth: each element enters and exits at most once. O(n) total.");
    }
}

Fixed Window — Maximum Sum Subarray of Size K

The fixed-size window, 1, 3, 2}; maintains a running sum. After the initial window is computed, each subsequent step adds the new right element and removes the element that left the window — both in O(1). This achieves O(n) overall versus O(n*k) brute force. The same pattern applies to maximum/minimum, average, or any aggregation over a window of fixed size.

package io.thecodeforge.algo;

public class MaxSumSubarrayFixedWindow {

    public static int maxSumSubarray(int[] arr, int k) {
        if (arr.length < k) {
            throw new IllegalArgumentException("Array length must be >= k");
        }

        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        int maxSum = windowSum;

        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i];
            windowSum -= arr[i - k];
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5        System.out.println(maxSumSubarray(arr, 3));  // 9
        System.out.println(maxSumSubarray(arr, 2));  // 6
    }
}

Variable Window — Longest Substring Without Repeating Characters

The variable window expands the right pointer unconditionally and shrinks the left pointer only when the constraint is violated. A hash map tracks the last seen index of each character. When a duplicate is encountered, move left to max(left, last_seen[char]+1) to skip past it — the max ensures left never moves backward. Update last_seen[char] after the left adjustment.

package io.thecodeforge.algo;

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueSubstring {

    /**
     * Finds the longest substring with no repeating characters.
     * Variable-size sliding window with HashMap tracking last-seen index.
     * O(n) time, O(min(n, alphabet)) space.
     */
    public static String longestNonRepeating(String text) {
        Map<Character, Integer> lastSeenAtIndex = new HashMap<>();
        int maxLength = 0;
        int windowStart = 0;
        int bestWindowStart = 0;

        for (int windowEnd = 0; windowEnd < text.length(); windowEnd++) {
            char currentChar = charAt(windowEnd, text);

            // If char was seen AND is inside current window, shrink left past it
            if (lastSeenAtIndex.containsKey(currentChar)
                    && lastSeenAtIndex.get(currentChar) >= windowStart) {
                windowStart = lastSeenAtIndex.get(currentChar) + 1;
            }

            lastSeenAtIndex.put(currentChar, windowEnd);

            int currentLength = windowEnd - windowStart + 1;
            if (currentLength > maxLength) {
                maxLength = currentLength;
                bestWindowStart = windowStart;
            }
        }

        return text.substring(bestWindowStart, bestWindowStart + maxLength);
    }

    private static char charAt(int index, String text) {
        return text.charAt(index);
    }

    public static void main(String[] args) {
        String[] tests = {"abcabcbb", "bbbbb", "pwwkew", "thecodeforge"};
        for (String input : tests) {
            String result = longestNonRepeating(input);
            System.out.printf("Input: %-15s → \"%s\" (length %d)%n",
                              "\"" + input + "\"", result, result.length());
        }
    }
}

Variable Window — At Most K Distinct Characters

The variable window expands the right pointer unconditionally and shrinks the left pointer only when the constraint is violated. A frequency map tracks the count of each character in the window. When the number of distinct characters exceeds k, shrink from the left by decrementing the left character's frequency and removing it from the map when the count reaches 0.

package io.thecodeforge.algo;

import java.util.HashMap;
import java.util.Map;

public class LongestSubstringKDistinct {

    /**
     * Finds the longest substring with at most k distinct characters.
     * Variable-size sliding window with frequency map.
     * O(n) time, O(k) space.
     */
    public static int longestSubstringKDistinct(String s, int k) {
        if (k == 0) return 0;

        Map<Character, Integer> freq = new HashMap<>();
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            char rightChar = s.charAt(right);
            freq.merge(rightChar, 1, Integer::sum);

            // Shrink window while constraint is violated
            while (freq.size() > k) {
                char leftChar = s.charAt(left);
                freq.merge(leftChar, -1, Integer::sum);
                if (freq.get(leftChar) == 0) {
                    freq.remove(leftChar);
                }
                left++;
            }

            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    /**
     * Converts 'exactly k distinct' to 'at most k' minus 'at most k-1'.
     * This is the standard trick for non-monotone constraints.
     */
    public static int exactlyKDistinct(String s, int k) {
        return longestSubstringKDistinct(s, k) - longestSubstringKDistinct(s, k - 1);
    }

    public static void main(String[] args) {
        System.out.println("At most 2 distinct in 'eceba': " + longestSubstringKDistinct("eceba", 2));       // 3
        System.out.println("At most 1 distinct in 'aa': " + longestSubstringKDistinct("aa", 1));             // 2
        System.out.println("At most 3 distinct in 'aabacbebebe': " + longestSubstringKDistinct("aabacbebebe", 3)); // 7
        System.out.println("Exactly 2 distinct in 'eceba': " + exactlyKDistinct("eceba", 2));                 // 3
        System.out.println("Exactly 3 distinct in 'eceba': " + exactlyKDistinct("eceba", 3));                 // 4
    }
}

Sliding Window Minimum — The Monotonic Deque Pattern

Finding the maximum or minimum of every window of size k is a classic problem. The naive approach scans all k elements in each window — O(n*k). A monotonic deque maintains candidates in sorted order, giving O(1) amortized per slide.

For maximum: maintain a deque of indices where values are in decreasing order. The front of the deque is always the maximum of the current window. When sliding, remove the front if it's outside the window, and remove all elements from the back that are smaller than the new element (they can never be the maximum while the new element is in the window).

package io.thecodeforge.algo;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class SlidingWindowMaximum {

    /**
     * Finds the maximum element in every window of size k.
     * Uses a monotonic deque — O(n) time, O(k) space.
     * Each element enters and exits the deque at most once.
     */
    public static int[] maxSlidingWindow(int[] arr, int k) {
        if (arr.length < k || k <= 0) return new int[0];

        int[] result = new int[arr.length - k + 1];
        Deque<Integer> deque = new ArrayDeque<>(); // stores indices, values in decreasing order

        for (int i = 0; i < arr.length; i++) {
            // Remove indices outside the current window
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // Remove all elements smaller than arr[i] from the back
            // They can never be the max while arr[i] is in the window
            while (!deque.isEmpty() && arr[deque.peekLast()] < arr[i]) {
                deque.pollLast();
            }

            deque.offerLast(i);

            // Window is complete — record the max (front of deque)
            if (i >= k - 1) {
                result[i - k + 1] = arr[deque.peekFirst()];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;

        int[] result = maxSlidingWindow(arr, k);
        System.out.println("Array: " + Arrays.toString(arr));
        System.out.println("Max in each window of size " + k + ": " + Arrays.toString(result));
        // [3, 3, 5, 5, 6, 7]
    }
}

How to Identify Sliding Window Problems — Before Your Interviewer Smells Blood

You don't need a checklist. You need pattern recognition. Every Sliding Window problem screams with the same tell: you're asked to process a contiguous sequence where the naive solution walks the same ground twice.

Look for three signals. First, the problem mentions subarray, substring, or window — that's the freebie. Second, the brute force O(n²) or O(n*k) solution feels obvious but painful. You're summing the same elements, counting the same characters, checking the same boundaries. Third — and this is the real tell — the solution should reuse a previous computation without re-scanning what's left behind.

Fixed window problems always give you k. Variable window problems never do — they ask for longest, shortest, or at-most constraints. If you see "maximum sum of any contiguous subarray" with no size, that's Kadane's, not sliding window. If you see "longest substring with at most K distinct characters" — that's your sliding window, and your window pointer just heard the starting gun.

// io.thecodeforge — dsa tutorial

public class SlidingWindowDetector {
    // Hueristic: count the clues before coding
    public static boolean isSlidingWindow(String problemStatement) {
        String lower = problemStatement.toLowerCase();
        boolean hasSubarrayOrSubstring = lower.contains("subarray") || lower.contains("substring") || lower.contains("window");
        boolean hasSizeConstraint = lower.contains("size k") || lower.contains("at most") || lower.contains("longest") || lower.contains("shortest");
        boolean hasContiguousRequirement = lower.contains("contiguous") || lower.contains("continuous") || lower.contains("consecutive");
        return hasSubarrayOrSubstring && (hasSizeConstraint || hasContiguousRequirement);
    }

    public static void main(String[] args) {
        String test = "Find the longest substring with at most K distinct characters";
        System.out.println("Is sliding window? " + isSlidingWindow(test)); // true
    }
}

Types of Sliding Window — Fixed vs. Variable, and Why Most Self-Taught Devs Get the Second Wrong

There are exactly two flavors, and they map directly to how you move the left pointer. Fixed window: left and right move in lockstep. You advance both by 1 each iteration. The window size never changes. Classic case: maximum sum subarray of size k. You add the new element, subtract the one that fell out, done.

Variable window: this is where careers stall. The right pointer grows until the constraint breaks (e.g., too many distinct characters), then you shrink from the left until the constraint is satisfied again. The window size fluctuates. The mistake juniors make? Shrinking one step at a time when they should be shrinking in a while loop. Or worse, resetting the entire window. The left pointer is the only way to maintain O(n) — every element enters once and exits once.

There's a third case you'll see in some problem sets: monotonic deque for sliding window minimum/maximum. That's not a different type of window — it's a different data structure inside the same variable-window pattern. Don't let the fancy name fool you. It's still just moving two pointers and maintaining an invariant.

// io.thecodeforge — dsa tutorial

public class SlidingWindowTypes {
    // Fixed: window size locked at k
    public static int maxSumFixed(int[] data, int k) {
        if (data.length < k) return 0;
        int sum = 0;
        for (int i = 0; i < k; i++) sum += data[i];
        int max = sum;
        for (int i = k; i < data.length; i++) {
            sum += data[i] - data[i - k];  // slide right, drop left
            max = Math.max(max, sum);
        }
        return max;
    }

    // Variable: right grows, left shrinks under constraint
    public static int maxDistinctChars(String s, int maxDistinct) {
        int[] freq = new int[256];
        int left = 0, count = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            if (freq[s.charAt(right)]++ == 0) count++;
            while (count > maxDistinct) {
                if (--freq[s.charAt(left++)] == 0) count--;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println("Fixed max: " + maxSumFixed(new int[]{1,2,3,4,5}, 3));
        System.out.println("Variable max: " + maxDistinctChars("aabbcc", 2));
    }
}

Sliding Window Minimum — The Monotonic Deque Pattern That Filters Out Weak Engineers

You've mastered sum and count. Now the interviewer hits you with: "Given an array and window size k, return the minimum in each window." The naive O(n*k) will get you ghosted. The sliding window minimum requires a different beast — a monotonic deque that maintains indices, not values.

Here's the why before the how: When a new element enters the window, any element to its left that is larger will never be the minimum again, because the new element is both smaller and will outlive them. So you pop from the back while the back's value >= current. Then push the current index. Then pop from the front if the index is out of the window. The front of the deque is always the minimum for the current window.

This trick works because you're not just sliding a window — you're maintaining a future-ranking of candidates. Each element is added once and removed once. O(n) total. The deque is your hit list. If you're asked for maximum, flip the comparison. Same pattern. Learn it once, use it for sliding window max, stock span, and every other "nearest greater element" variant that looks unrelated but isn't.

// io.thecodeforge — dsa tutorial

import java.util.ArrayDeque;
import java.util.Deque;

public class SlidingWindowMinDeque {
    public static int[] minSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0) return new int[0];
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();  // stores indices, not values

        for (int i = 0; i < n; i++) {
            // remove indices out of current window (from front)
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1)
                deque.pollFirst();

            // remove from back: any larger element won't be min while this smaller one exists
            while (!deque.isEmpty() && nums[deque.peekLast()] >= nums[i])
                deque.pollLast();

            deque.offerLast(i);

            // first window completes at index k-1
            if (i >= k - 1)
                result[i - k + 1] = nums[deque.peekFirst()];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] mins = minSlidingWindow(nums, k);
        for (int m : mins) System.out.print(m + " ");
    }
}

The Only Sliding Window Template You'll Ever Need — Why Switching Between Fixed and Variable Costs You Zero Rework

Most devs memorize a separate template for fixed and variable windows. That's cargo culting. The sliding window technique is one pattern with one job: maintain a contiguous subset of data that satisfies a condition. The only difference is how tight you hold the condition.

Here's the production insight — use a while loop for the shrink phase, not an if. When you use if, you break the invariant on variable windows where the window can shrink by more than one element. I've fixed more bugs from that single line than anything else.

The template does three things: expand the right pointer, update state, then shrink the left pointer until the condition holds. Track the answer either before or after shrinking depending on whether you want the largest valid window or the smallest invalid one. That's it. Memorize this and you stop caring what the problem calls itself.

// io.thecodeforge — dsa tutorial

public int slidingWindow(int[] arr, int k) {
    int left = 0, answer = 0;
    int state = 0;
    
    for (int right = 0; right < arr.length; right++) {
        // Expand
        state += arr[right];
        
        // Shrink — use while, not if
        while (state > k) {
            state -= arr[left];
            left++;
        }
        
        // Record answer (valid window state after shrink)
        answer = Math.max(answer, right - left + 1);
    }
    return answer;
}

Common Mistakes That Get Your Sliding Window Solution Torched in Code Review — And How to Fix Them

I've reviewed hundreds of sliding window submissions. The same three mistakes keep showing up.

First: using an if statement to shrink the window in a variable-length problem. When the window can shrink by more than one element, if breaks immediately. The inner while loop isn't negotiable. Second: tracking the answer before shrinking instead of after, or vice versa, without understanding the difference. If you need the smallest window that violates a condition, record before shrink. If you need the largest valid window, record after shrink. Mixing these up wastes hours.

Third: forgetting to update all state during shrink. You collapse the window but leave stale counters, pointers, or sum values. Then you debug for an hour wondering why your condition never holds. Treat shrink like a transaction — update everything when you move left.

Every one of these mistakes is a 10-minute fix in isolation but a career-limiting look in an interview.

// io.thecodeforge — dsa tutorial

// WRONG — if instead of while
public int wrongExample(String s) {
    int left = 0, maxLen = 0;
    Set<Character> set = new HashSet<>();
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        // if breaks when multiple removals needed
        if (set.contains(c)) {
            set.remove(s.charAt(left));
            left++;
        }
        set.add(c);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen; // fails on "abba"
}

// CORRECT
public int correctExample(String s) {
    int left = 0, maxLen = 0;
    Set<Character> set = new HashSet<>();
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        while (set.contains(c)) {
            set.remove(s.charAt(left));
            left++;
        }
        set.add(c);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen; // returns 3 for "abba"
}

Visual Intuition — Why Your Brain Needs a Window, Not a Frame

Sliding window is harder to grasp in code because you're managing indices instead of visualizing the range. The fix: draw a physical window. Imagine a strip of paper with numbers. Your window is a cardboard frame that slides left to right. For fixed window (size k), the frame is rigid — you move it one step, drop the leftmost number, add the next rightmost. For variable window, the frame is elastic: expand right to include new data, shrink left to drop constraints. This maps directly to two-pointer logic: left and right are the frame edges. Every time you expand right, you add to your window sum or set. Every time you shrink left, you remove. The deque for minimums is just a second mini-window inside tracking the smallest value. Without this visual anchor, developers confuse shrinking with resetting or treat window boundaries as exclusive vs inclusive incorrectly. Draw it once, code it once — the pattern sticks.

// io.thecodeforge — dsa tutorial

public class SlidingWindowVisual {
    public int maxSumFixed(int[] arr, int k) {
        int sum = 0, max = 0;
        for (int i = 0; i < k; i++) sum += arr[i];
        max = sum;
        for (int i = k; i < arr.length; i++) {
            sum += arr[i] - arr[i - k];
            max = Math.max(max, sum);
        }
        return max;
    }
}

Network Traffic Monitoring — Real-Time Anomaly Detection with Fixed Window

Network engineers monitor packets per second (PPS) to detect DDoS attacks. A fixed sliding window of size 60 seconds tracks the count of packets. Each second, a new count arrives and the oldest drops out. The window sum updates in O(1): add new, subtract old. If PPS exceeds threshold (e.g., 10,000), raise alert. This is Maximum Sum Subarray of Size K applied to live data — but instead of max, you check thresholds. The challenge: timestamps aren't perfectly aligned. Use a circular buffer of 60 buckets, each holding one second's count. On each tick, overwrite the oldest bucket and recompute total. This avoids garbage collection from queue operations. False positives spike at minute boundaries if you use naive hour reset — sliding window eliminates that boundary leak. Real implementations in NetFlow/IPFIX collectors use this pattern for near-instant threshold alerts without storing all raw packets.

// io.thecodeforge — dsa tutorial

public class TrafficMonitor {
    private int[] buckets = new int[60];
    private int idx = 0;
    private long total = 0;
    public void tick(int packets) {
        total -= buckets[idx];
        total += packets;
        buckets[idx] = packets;
        idx = (idx + 1) % 60;
        if (total > 10_000) alert();
    }
    private void alert() { /* notify */ }
}

Essential LeetCode Problems & Solutions

Mastering the sliding window technique requires pattern recognition across classic problems. Start with LeetCode 125 Valid Palindrome — a simple two-pointer verification that checks characters from both ends, skipping non-alphanumerics. LeetCode 11 Container With Most Water uses two pointers shrinking from the edges, always moving the shorter line inward to maximize area without O(n²) brute force. LeetCode 15 3Sum demands sorting plus a fixed outer loop with two-pointer inner search, avoiding duplicates by skipping identical values. LeetCode 42 Trapping Rain Water tracks left and right max heights, moving the pointer with the smaller max to accumulate trapped water per column. LeetCode 567 Permutation in String applies a fixed-size frequency array sliding over s2, shrinking when counts exceed s1's tally, then checking for exact match. These five problems cover fixed window (567), variable window (42, 11), and multi-pointer (15) patterns. Work through them in order: palindrome builds basic pointer discipline, container adds optimization, 3Sum introduces triplet handling, rain water teaches height tracking, and permutation cements frequency sliding. Each solution reuses the same pointer mechanics with different state tracking, proving the technique's versatility across difficulty levels.

// io.thecodeforge — dsa tutorial
import java.util.*;
public class ThreeSumSolution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates
            int lo = i + 1, hi = nums.length - 1, sum = -nums[i];
            while (lo < hi) {
                if (nums[lo] + nums[hi] == sum) {
                    res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                    while (lo < hi && nums[lo] == nums[++lo]);
                    while (lo < hi && nums[hi] == nums[--hi]);
                } else if (nums[lo] + nums[hi] < sum) lo++;
                else hi--;
            }
        }
        return res;
    }
}

Multi-Pointer Pattern (3Sum)

The multi-pointer pattern extends sliding window to three or more pointers, solving problems like 3Sum (LeetCode 15) where a single loop doesn't suffice. The core idea: fix one pointer (usually the leftmost) and apply a two-pointer sliding window on the remainder of the array. Sorting is mandatory — it transforms the unsorted triple search into a monotonic space where moving pointers predictably changes the sum. For 3Sum, fix i from 0 to n-3, then set lo = i+1 and hi = n-1. The window slides inward based on the comparison of nums[i] + nums[lo] + nums[hi] to zero. When the sum matches, record the triplet and advance both lo and hi past duplicates. When too low, increment lo to increase sum; too high, decrement hi. This pattern generalizes: 3Sum Closest (LeetCode 16) tracks the best delta without exact match, 4Sum (LeetCode 18) nests an additional fixed pointer, and Two Sum II (LeetCode 167) uses only two pointers on sorted array. The key insight is that each additional pointer reduces the problem dimension by one — you trade O(n^k) brute force for O(n^(k-1)) with pointers. Implement this pattern whenever you need combinations from a sorted dataset with a monotonic property.

// io.thecodeforge — dsa tutorial
import java.util.*;
public class ThreeSumClosest {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closest = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            int lo = i + 1, hi = nums.length - 1;
            while (lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if (Math.abs(sum - target) < Math.abs(closest - target))
                    closest = sum;
                if (sum < target) lo++;
                else if (sum > target) hi--;
                else return target;
            }
        }
        return closest;
    }
}

Performance Optimization Tips

Optimizing sliding window algorithms focuses on reducing constant factors and eliminating redundant work. Early termination in two pointers: after sorting, if the smallest possible sum (leftmost unprocessed values) already exceeds the target, break the outer loop entirely — no further combinations can work. Similarly, if the largest possible sum is below target, continue the loop but skip inner pointer work. This prunes large portions of the search space in problems like 3Sum Closest or Two Sum II. Avoiding redundant calculations means caching repeated arithmetic: when computing running sums, update incrementally (add new element, subtract evicted element) instead of recalculating from scratch. For maximum window problems like Container With Most Water, compute area once per iteration, not per subarray — track max left/right heights with single variables, not arrays. In frequency-based sliding (Permutation in String), use an integer array of size 26 for character counts rather than HashMap — array access is O(1) with negligible overhead. For monotonic deque patterns (Sliding Window Maximum), insert and remove from deque ends in O(1) amortized, avoiding O(k) window scans. Apply greedy pointer movement: in trapping rain water, always advance the pointer with the smaller boundary height — this minimizes unnecessary comparisons and eliminates extra memory for tracking both maxes simultaneously. These micro-optimizations compound across large inputs, transforming O(n) into O(n) with 3x-10x real-world speedup.

// io.thecodeforge — dsa tutorial
public class ContainerMostWater {
    public int maxArea(int[] height) {
        int lo = 0, hi = height.length - 1, max = 0;
        while (lo < hi) {
            int w = hi - lo;
            int h = Math.min(height[lo], height[hi]);
            max = Math.max(max, w * h);
            if (height[lo] < height[hi]) lo++;  // move shorter line inward
            else hi--;
        }
        return max;
    }
}