Sliding Window Technique: From O(n·k) Scans to O(n) in One Pass

Scenario context

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 regardles…

This walkthrough focuses on The k-Consecutive-Elements Problem: One Pattern Behind Thousands of Interviews.

Before making a design choice, clarify:

• 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.
• For k=1,000 and n=1,000,000 that's a billion additions.

Concepts in play: jvm-internals-and-garbage-collection, core-algorithm-patterns, stack-and-queue-data-structures, hash-tables-and-bloom-filters

Stage 1 — Expand and Shrink: The Mechanics of a Variable Sliding Window

• The canonical variable-window template in Java: 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.

// 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);
}

Observable outcome: Total O(n) — amortized O(1) per element.

Stage 2 — Visualizing Window Expansion and Contraction

• 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.

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 right++]
    C --> D{Window violates constraint?}
    D -- Yes --> E[Remove arr left from window state left++]
    E --> D
    D -- No --> F[Update result with current window left to right-1]
    F --> B

Observable outcome: 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.

Stage 3 — 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.

Observable outcome: 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.

Stage 4 — Four Java Implementations: Fixed and Variable Windows

• Problem 1: Maximum Sum Subarray of Size K (Fixed Window) Problem 2: Longest Substring Without Repeating Characters (Variable Window) Problem 3: Smallest Subarray with Sum ≥ S (Variable Window) Shrink direction matters h…
• 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)

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)
    }
}

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")
    }
}

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

Stage 5 — 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): Under the hood, Kafka Streams maintains a RocksDB-backed state store per…
• 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.

// 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");

Observable outcome: When a window's end time passes (plus a configurable grace period), its aggregated state is emitted downstream.

End-to-end outcome

After working through the stages, you should be able to explain:

• Confusing the shrink direction for minimum vs.
• For longest (maximum) windows, shrink when the window is invalid.
• • Fixed window slides in O(1) per step: add the incoming element, subtract the outgoing element.
• • Variable window expands greedily on the right and shrinks on the left when the constraint is violated.

Alternatives considered

Fixed vs. Variable Windows: Two Flavors of One Idea

Fixed window: The window always has exactly k elements.

Fixed vs. Variable Window: The Decision Guide

Is the window size fixed or does it depend on a constraint?

Failure and degraded modes

The source does not isolate a separate failure mode. Limits that matter for the scenario are called out in the stage decisions above.