TLDR: Instead of recomputing a subarray aggregate from scratch on every shift, maintain it incrementally — add the incoming element, remove the outgoing element. For a fixed window this costs O(1) per shift. For a variable window, expand the right boundary until a condition is met, then shrink the left boundary until the condition breaks. Every element enters and leaves the window at most once, giving O(n) total regardless of window size.

---

📖 The k-Consecutive-Elements Problem: One Pattern Behind Thousands of Interviews

You need to find the maximum sum of any k consecutive elements in an array of n integers. The brute-force approach computes the sum of each window of size k independently: for each of the n−k+1 starting positions, sum k elements. That's O(n·k) operations. For k=1,000 and n=1,000,000 that's a billion additions.

Here's the insight that makes it O(n): consecutive windows of size k overlap in k−1 elements. When you slide from window [i, i+k-1] to [i+1, i+k], you're adding one element (arr[i+k]) and removing one element (arr[i]). The sum of the new window is previous_sum - arr[i] + arr[i+k]. One subtraction, one addition — regardless of k.

This incremental maintenance idea is the sliding window technique. It appears in two flavors:

Both reduce to the same O(n) amortized cost. The variable window is the more powerful and more interview-tested variant.

---

🔍 Fixed vs. Variable Windows: Two Flavors of One Idea

Fixed window: The window always has exactly k elements. You initialize it over arr[0..k-1], then slide it right one element at a time by adding arr[right] and removing arr[left]. The window boundaries move together, always k elements apart. This is the simplest form — no condition logic, just constant-time updates.

Variable window: The window grows from the right (add elements) until a constraint is violated, then shrinks from the left (remove elements) until the constraint is restored. The window size fluctuates. The trick is identifying the shrink condition: the exact moment the window becomes invalid and needs left-boundary movement.

Common shrink conditions:

• Longest substring without repeating characters → shrink when a character appears twice.
• Smallest subarray with sum ≥ S → shrink while the current sum still satisfies sum ≥ S (you're looking for the smallest valid window).
• Longest substring with at most K distinct characters → shrink when the distinct-character count exceeds K.

The shrink condition is the key design decision. Get it right and the rest of the algorithm is mechanical.

---

⚙️ Expand and Shrink: The Mechanics of a Variable Sliding Window

The canonical variable-window template in Java:

// Generic variable-window template
int left = 0;
int windowState = 0; // e.g., current sum, char frequency map, distinct count

int result = 0;

for (int right = 0; right < arr.length; right++) {
    // 1. Expand: add arr[right] to the window
    windowState = add(windowState, arr[right]);

    // 2. Shrink: while the window violates the constraint, move left inward
    while (isInvalid(windowState)) {
        windowState = remove(windowState, arr[left]);
        left++;
    }

    // 3. The window [left, right] is now valid — update result
    result = Math.max(result, right - left + 1);
}

The outer for loop advances right exactly n times. The inner while loop advances left at most n times total across the entire run (left never moves backward). Together: every element enters the window once and leaves once. Total O(n) — amortized O(1) per element.

This amortized argument is the core insight. Even if the while loop runs multiple times on a given iteration, those iterations "spent" left-pointer advances that will not be repeated on future iterations.

---

🧠 Deep Dive: What the Window State Contains and Why Amortization Holds

The Internals: Data Structures Inside the Window

The "window state" in the template above is abstract. The actual data structure you use inside the window depends on what the constraint tests:

Sum-based constraints (max sum, sum ≥ S): The state is a single integer. Add arr[right], subtract arr[left]. O(1) per boundary move. Space: O(1).

Frequency-based constraints (no repeating characters, at most K distinct): The state is a HashMap<Character, Integer> or a fixed-size int[26] array. Increment on add, decrement on remove (delete the key if count reaches zero). O(1) per move with a hash map. Space: O(character set size).

Monotonic deque constraints (maximum/minimum in every window): The state is a Deque<Integer> maintaining indices in decreasing order. When a new element arrives, pop all indices from the back with smaller values before pushing the new one. Pop from the front when the front index falls outside the window. O(1) amortized per element. Space: O(k) for a fixed window of size k.

Each element is pushed at most once and popped at most once from the deque, giving O(n) total — even though a single iteration might trigger multiple pops.

Performance Analysis: Why Each Element Is Visited at Most Twice

Formal argument for the variable window:

The right pointer starts at 0 and advances to n−1 — exactly n increments total.

The left pointer starts at 0. It never decreases. It therefore makes at most n total increments across the entire algorithm (since it can never exceed right, which reaches n−1).

The inner while loop body runs exactly as many times as left increments across the entire algorithm — at most n times total.

Therefore the total number of operations is at most n (outer loop) + n (inner while loop total) = O(n).

---

📊 Visualizing Window Expansion and Contraction

flowchart TD
    A([Start: left=0, right=0, state=empty]) --> B{right < n?}
    B -- No --> Z([Return result])
    B -- Yes --> C[Add arr right to window state\nright++]
    C --> D{Window violates\nconstraint?}
    D -- Yes --> E[Remove arr left from window state\nleft++]
    E --> D
    D -- No --> F[Update result with\ncurrent window left to right-1]
    F --> B

Right expands unconditionally each outer iteration. Left shrinks only while the constraint is violated. Every element enters and exits exactly once.

Worked trace on "abcabcbb" — Longest Substring Without Repeating Characters:

Each "→" in left column represents one or more left-pointer advances triggered by a duplicate entry.

---

🌍 Subarray Problems in Production: Where Sliding Window Appears

The sliding window is one of the most practically-used algorithmic patterns outside competitive programming:

Network traffic analysis: A sliding window over the last N seconds of log entries computes rolling throughput, error rates, and latency percentiles. Each new log entry enters the window; entries older than the cutoff exit. The window state is a running sum or histogram.

Rate limiting (token bucket / leaky bucket): A variable window tracks request timestamps. The constraint is "at most K requests in any rolling time window." When a new request arrives, the left pointer advances to remove timestamps older than the window cutoff. If the current count exceeds K, the request is rejected. This is exactly the variable-window shrink pattern applied to time-series data.

DNA sequence analysis: Finding the longest subsequence with at most K mismatches between a probe and a genome reference is a variable-window problem. The alphabet is {A, T, C, G}. The constraint is mismatch count ≤ K. The window state is a frequency comparison array.

Stream analytics (Apache Kafka, Apache Flink): Event-time windows in stream processing are a direct implementation of this pattern at distributed scale. A tumbling window is a fixed window; a sliding window in stream processing maps directly to the fixed-window variant. A session window maps to the variable window.

---

⚖️ When the Window Approach Breaks Down

Non-contiguous subarrays: Sliding window only applies to contiguous subarrays or substrings. If the problem asks for subsequences (non-contiguous selections), you need dynamic programming.

Two-dimensional arrays: The standard single-axis window doesn't extend directly to 2D arrays. To find the maximum sum submatrix of size k×k, you can collapse each column strip into a 1D prefix sum and then slide a window over those prefix sums, but this requires the additional preprocessing step.

Constraints that require future knowledge: The window works because the validity of adding arr[right] can be tested immediately with the current window state. If the validity test requires knowing future elements, the window pattern doesn't apply.

Non-monotonic shrink conditions: The inner while loop assumes that once the window is valid after shrinking, adding one more element from the right can make it invalid again but never "more valid" than it currently is. If adding an element can both increase and decrease the validity metric non-monotonically, the shrink condition has no simple threshold and the while loop can't stop reliably.

---

🧭 Fixed vs. Variable Window: The Decision Guide

The decisive questions:

1. Is the window size fixed or does it depend on a constraint? → Fixed or variable.
2. What is my shrink condition? If you can't state it as a single testable inequality, reconsider the pattern.
3. Does my window state fit in O(1) or O(alphabet size) space? If it requires O(n) space, hash map is likely the right structure and the window still runs O(n) total.

---

🧪 Four Java Implementations: Fixed and Variable Windows

Problem 1: Maximum Sum Subarray of Size K (Fixed Window)

public class MaxSumSubarrayK {
    /**
     * Find the maximum sum of any contiguous subarray of exactly size k.
     * Time: O(n)  Space: O(1)
     */
    public int maxSum(int[] arr, int k) {
        if (arr.length < k) throw new IllegalArgumentException("Array smaller than window");

        // Build the 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 right = k; right < arr.length; right++) {
            windowSum += arr[right] - arr[right - k];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        MaxSumSubarrayK solver = new MaxSumSubarrayK();
        System.out.println(solver.maxSum(new int[]{2, 1, 5, 1, 3, 2}, 3)); // 9 (5+1+3)
        System.out.println(solver.maxSum(new int[]{2, 3, 4, 1, 5}, 2));    // 7 (3+4)
    }
}

---

Problem 2: Longest Substring Without Repeating Characters (Variable Window)

import java.util.HashMap;

public class LongestSubstringNoRepeats {
    /**
     * LeetCode 3 — Longest Substring Without Repeating Characters
     * Shrink condition: a character appears more than once in the window.
     * Time: O(n)  Space: O(min(n, alphabet))
     */
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> charCount = new HashMap<>();
        int left = 0;
        int maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            charCount.merge(c, 1, Integer::sum); // add to window

            // Shrink while duplicate exists
            while (charCount.get(c) > 1) {
                char leftChar = s.charAt(left);
                charCount.merge(leftChar, -1, Integer::sum);
                if (charCount.get(leftChar) == 0) charCount.remove(leftChar);
                left++;
            }

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

    public static void main(String[] args) {
        LongestSubstringNoRepeats solver = new LongestSubstringNoRepeats();
        System.out.println(solver.lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")
        System.out.println(solver.lengthOfLongestSubstring("bbbbb"));    // 1 ("b")
        System.out.println(solver.lengthOfLongestSubstring("pwwkew"));   // 3 ("wke")
    }
}

---

Problem 3: Smallest Subarray with Sum ≥ S (Variable Window)

public class SmallestSubarrayWithSumS {
    /**
     * LeetCode 209 — Minimum Size Subarray Sum
     * Shrink condition: sum >= s (keep shrinking as long as constraint holds —
     *                  you're looking for the SMALLEST valid window).
     * Time: O(n)  Space: O(1)
     */
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int windowSum = 0;
        int minLen = Integer.MAX_VALUE;

        for (int right = 0; right < nums.length; right++) {
            windowSum += nums[right];

            // Shrink greedily while the window satisfies the constraint
            while (windowSum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                windowSum -= nums[left];
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

    public static void main(String[] args) {
        SmallestSubarrayWithSumS solver = new SmallestSubarrayWithSumS();
        System.out.println(solver.minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3})); // 2 ([4,3])
        System.out.println(solver.minSubArrayLen(4, new int[]{1, 4, 4}));           // 1 ([4])
        System.out.println(solver.minSubArrayLen(11, new int[]{1, 1, 1, 1, 1}));    // 0 (impossible)
    }
}

Shrink direction matters here. For longest windows you shrink when the window is invalid. For shortest windows you shrink when the window is valid, recording the length before shrinking.

---

Problem 4: Longest Substring with At Most K Distinct Characters (Variable Window)

import java.util.HashMap;

public class LongestSubstringKDistinct {
    /**
     * LeetCode 340 — Longest Substring with At Most K Distinct Characters
     * Shrink condition: distinct character count in window exceeds K.
     * Time: O(n)  Space: O(K)
     */
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (k == 0) return 0;
        HashMap<Character, Integer> charCount = new HashMap<>();
        int left = 0;
        int maxLen = 0;

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

            // Shrink while distinct characters exceed K
            while (charCount.size() > k) {
                char leftChar = s.charAt(left);
                charCount.merge(leftChar, -1, Integer::sum);
                if (charCount.get(leftChar) == 0) charCount.remove(leftChar);
                left++;
            }

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

    public static void main(String[] args) {
        LongestSubstringKDistinct solver = new LongestSubstringKDistinct();
        System.out.println(solver.lengthOfLongestSubstringKDistinct("eceba", 2)); // 3 ("ece")
        System.out.println(solver.lengthOfLongestSubstringKDistinct("aa", 1));    // 2 ("aa")
    }
}

---

🛠️ How Apache Kafka Streams Implements Window Semantics

Apache Kafka Streams, an open-source stream processing library, directly implements the sliding window abstraction at the distributed systems level. Its TimeWindows class supports both tumbling windows (fixed, non-overlapping) and hopping windows (fixed size, slides by a smaller hop interval):

// Kafka Streams: count events in a rolling 5-minute window, sliding every 1 minute
KStream<String, Event> events = builder.stream("input-topic");

events
    .groupByKey()
    .windowedBy(
        SlidingWindows.ofTimeDifferenceWithNoGrace(Duration.ofMinutes(5))
    )
    .count()
    .toStream()
    .to("output-topic");

Under the hood, Kafka Streams maintains a RocksDB-backed state store per window. When a new event arrives with timestamp t, it is included in all windows whose [start, end] range contains t. When a window's end time passes (plus a configurable grace period), its aggregated state is emitted downstream. The "add element on right, remove element on left" pattern from the array algorithm maps directly to "include in active windows, evict from closed windows."

The key difference from the in-memory array implementation: Kafka's windows are keyed by event time, not array index. But the amortized O(1) per-event cost survives the abstraction — each event enters exactly one window-set and eventually exits it.

For a deeper look at stream processing with Kafka Streams, see the companion post on stream processing pipeline patterns.

---

📚 Lessons Learned: The Shrink Condition Is Everything

1. Confusing the shrink direction for minimum vs. maximum windows. For longest (maximum) windows, shrink when the window is invalid. For shortest (minimum) windows, shrink when the window is still valid — you record the length before shrinking because a valid window might get shorter. Getting this backward produces an answer that's always 0 or always too large.

2. Not removing the character from the map when its count reaches zero. In character-frequency problems, leaving zero-count entries in the HashMap causes charCount.size() to return the number of keys ever added rather than the number of distinct characters currently in the window. Always call remove() when a character's count hits zero.

3. Applying the pattern to non-contiguous subsequence problems. Sliding window requires contiguity. If the problem says "subsequence" (not "subarray" or "substring"), the window shrink logic breaks down because you can skip elements. Reach for dynamic programming instead.

4. Forgetting to initialize the first fixed window. For the fixed-window variant, you must sum the first k elements before entering the slide loop. The loop body assumes a previous window sum already exists. Skipping this produces windowSum = 0 as the starting point, which corrupts every subsequent result.

5. Using right - left instead of right - left + 1 for window length. A window from index 2 to index 5 has length 4 (indices 2, 3, 4, 5). The formula is right - left + 1. Using right - left gives 3 — always one too small. This off-by-one is extremely common in interview settings.

---

📌 Summary and Key Takeaways

• Fixed window slides in O(1) per step: add the incoming element, subtract the outgoing element. Total: O(n).
• Variable window expands greedily on the right and shrinks on the left when the constraint is violated. Every element enters and leaves at most once: O(n) amortized.
• The shrink condition is the design decision. Identify it precisely before writing code. It determines whether the inner while loop terminates correctly and whether you're looking for a maximum or minimum window.
• Window state can be more than a sum. Frequency maps, monotonic deques, and distinct-count trackers all fit the pattern — each with O(1) amortized per-element cost.
• The pattern breaks on non-contiguous subsequences. If elements can be skipped, the window's left/right boundary logic doesn't apply. Switch to dynamic programming.
• Industry applications are everywhere: rate limiting, rolling analytics, network traffic monitoring, and stream processing all use the same expand-and-shrink logic at distributed scale.

---

📝 Practice Quiz

1. You use a fixed-window of size k to find the maximum sum subarray. What is the correct formula for the new window sum when sliding from position i to i+1?

   • A) newSum = windowSum + arr[i + k]
   • B) newSum = windowSum + arr[i + k] - arr[i]
   • C) newSum = windowSum - arr[i + k] + arr[i] Correct Answer: B — The new window gains arr[i+k] (right boundary enters) and loses arr[i] (left boundary exits). So newSum = windowSum + arr[i+k] - arr[i].

2. In "Smallest Subarray with Sum ≥ S," the shrink condition triggers while windowSum >= target. Why do you shrink while the constraint holds rather than while it's violated (as you would for a longest-window problem)?

   • A) Because you want to find the maximum window, and shrinking while valid ensures maximum length.
   • B) Because you are looking for the minimum valid window — shrinking while the window is still valid finds shorter windows that still satisfy the constraint before the constraint breaks.
   • C) Because the constraint is non-monotonic and requires bidirectional pointer movement. Correct Answer: B — For minimum-window problems, you greedily shrink the window as long as it remains valid, recording the (shrinking) length at each step. When the constraint finally breaks, you've found the shortest window for this right-boundary position.

3. Which data structure should the window state use for "Longest Substring with At Most K Distinct Characters," and why does it handle the shrink step in O(1) amortized time?

   • A) A sorted TreeMap — supports O(log n) insertion and O(log n) deletion.
   • B) A HashMap from character to count — O(1) average insertion/deletion; removing a key when count hits zero keeps the size equal to the current distinct-character count.
   • C) A HashSet of characters — O(1) insertion but cannot track duplicates needed for correct window shrinking. Correct Answer: B — The HashMap tracks per-character frequency. Removing a key when its count drops to zero ensures map.size() equals the number of distinct characters in the window at all times.

4. Open-ended challenge: The monotonic deque variant of the sliding window solves "Maximum of every k-size window" in O(n) total. Standard sliding window with a plain max() call would be O(n·k). Explain how the deque maintains the invariant that its front always holds the maximum of the current window. What guarantees the deque operations are O(1) amortized rather than O(k) per element? Would this same deque approach work for a variable-size window? What changes?

---

🔗 Related Posts

• Two Pointer Technique — the foundational two-boundary idea that sliding window extends with a running aggregate and a shrink condition.
• Fast and Slow Pointer — the same-direction variant of two pointers specialized for cycle detection and midpoint finding in linked structures.
• Backtracking Explained — a complementary search pattern for problems requiring exhaustive exploration with constraint-based pruning.

---