Sliding Window — LinkedList Race Condition in Averages

Sliding window problems show up in almost every technical interview at top-tier companies — not because they're obscure, but because they test whether you think algorithmically or just mechanically. The naive solution to most array and string problems is O(n²) nested loops. The sliding window technique collapses that to O(n), and interviewers use these problems specifically to see if you can make that leap without prompting.

The core problem it solves is this: any time you need to examine a contiguous subarray or substring under some constraint — maximum sum, longest without repeating characters, smallest with a target sum — you're repeatedly looking at overlapping data. Brute force recalculates that overlapping data every single iteration. A sliding window maintains just enough state so you only ever process each element once as the window expands and once as it contracts.

By the end of this article you'll be able to recognise which of the two main window types (fixed-size vs dynamic) applies to a given problem, implement both from memory, handle the edge cases that trip up even experienced candidates, and answer the follow-up questions interviewers use to separate good solutions from great ones.

The Sliding Window: A Pointer Dance That Avoids Recalculation

The sliding window technique maintains a contiguous subarray (or substring) by moving two pointers — left and right — across a linear data structure. Instead of recomputing from scratch for each possible subarray (O(n²) or worse), you update the window's aggregate value incrementally as it expands or contracts. This yields O(n) time and O(1) or O(k) space, where k is the window size.

Two key properties make this work: the window's boundaries move monotonically (no backtracking), and the aggregate function must be efficiently updatable — typically via addition/subtraction (sum, count) or a deque (min, max). The right pointer advances to include new elements; the left pointer advances to exclude old ones when the window violates a constraint (e.g., exceeds a target sum or fixed size).

Use sliding window when the problem asks for a contiguous subarray's property under a constraint — maximum sum of size k, longest substring without repeating characters, or average of every k-length subarray. In production, this pattern appears in real-time metrics (e.g., rolling average latency over the last 1000 requests) where recomputing the full window per event would be too expensive.

Fixed-Size Windows — When the Frame Never Changes

A fixed-size window is the simpler of the two patterns. The window length is given to you upfront and never changes — your only job is to slide it across the array one step at a time and track whatever metric you care about.

The key insight is how you update the window in O(1) instead of O(k): when the window moves one position to the right, exactly one element leaves the left edge and one enters the right edge. That means you don't need to sum (or hash, or count) the whole window again — you just subtract the outgoing element and add the incoming one.

This pattern covers problems like: maximum average subarray of length k, maximum sum subarray of length k, count of anagram occurrences in a string, and find all substrings containing exactly k distinct characters with a fixed length.

The implementation template is always the same: build the first window, record your answer, then loop from index k to n-1, sliding by one each iteration. Get that template into muscle memory and the code almost writes itself.

package io.thecodeforge.algorithms;

public class MaxSumFixedWindow {

    /**
     * Finds the maximum sum of any contiguous subarray of exactly 'windowSize' elements.
     * Time:  O(n)  — each element is added once and removed once
     * Space: O(1)  — no extra data structures needed
     */
    public static int findMaxSum(int[] prices, int windowSize) {
        int totalElements = prices.length;

        // Edge case: window is larger than the array itself
        if (windowSize > totalElements) {
            throw new IllegalArgumentException(
                "Window size " + windowSize + " exceeds array length " + totalElements
            );
        }

        // Step 1: Build the first window by summing the first 'windowSize' elements
        int currentWindowSum = 0;
        for (int i = 0; i < windowSize; i++) {
            currentWindowSum += prices[i];
        }

        // The first window is our baseline best answer
        int maxSum = currentWindowSum;

        // Step 2: Slide the window one position at a time across the rest of the array
        for (int rightEdge = windowSize; rightEdge < totalElements; rightEdge++) {
            int leftEdge = rightEdge - windowSize; // the element we're dropping off the left

            // Drop the outgoing element, add the incoming element — one operation each
            currentWindowSum += prices[rightEdge];   // new element entering from the right
            currentWindowSum -= prices[leftEdge];    // old element leaving from the left

            // Update our best answer if this window beats it
            maxSum = Math.max(maxSum, currentWindowSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] dailyStockPrices = {12, 5, 35, 8, 6, 14, 21, 9, 3, 18, 27, 11, 4, 16};
        int targetWindowDays = 4;

        int result = findMaxSum(dailyStockPrices, targetWindowDays);
        System.out.println("Stock prices: " + java.util.Arrays.toString(dailyStockPrices));
        System.out.println("Max 4-day sum: " + result);
    }
}

Dynamic Windows — When the Frame Grows and Shrinks Based on a Condition

Dynamic (or variable-size) windows are where most candidates stumble, because the window doesn't have a fixed length — it grows until it violates a constraint, then shrinks from the left until it's valid again. The two-pointer approach drives this: a right pointer expands the window, and a left pointer contracts it.

The mental model that makes this click: think of the right pointer as greedy and optimistic — it keeps consuming elements hoping to satisfy or maximise the target. The left pointer is the enforcer — when the window breaks the rules, it evicts elements from the left until the window is valid again.

This pattern handles: longest substring without repeating characters, minimum size subarray with sum ≥ target, longest subarray with at most k distinct characters, and fruit into baskets (same idea, different flavour).

The critical implementation detail is the order of operations inside the loop: expand right first, update your state, then shrink left in a while loop until valid, then record your answer. Get that order wrong and you'll record invalid states or miss valid ones — a bug that's devilishly hard to spot under interview pressure.

package io.thecodeforge.algorithms;

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

public class LongestSubstringKDistinct {

    /**
     * Finds the length of the longest substring with at most 'maxDistinct' distinct characters.
     * Time:  O(n)  — each pointer travels the array once
     * Space: O(k)  — where k is the number of distinct characters allowed
     */
    public static int findLongest(String text, int maxDistinct) {
        if (text == null || text.isEmpty() || maxDistinct == 0) return 0;

        Map<Character, Integer> charFrequencyInWindow = new HashMap<>();
        int leftPointer = 0, longestFound = 0;

        for (int rightPointer = 0; rightPointer < text.length(); rightPointer++) {
            char incomingChar = text.charAt(rightPointer);
            charFrequencyInWindow.put(incomingChar, charFrequencyInWindow.getOrDefault(incomingChar, 0) + 1);

            // Shrink from the left until we're back to maxDistinct distinct chars
            while (charFrequencyInWindow.size() > maxDistinct) {
                char outgoingChar = text.charAt(leftPointer);
                charFrequencyInWindow.put(outgoingChar, charFrequencyInWindow.get(outgoingChar) - 1);

                if (charFrequencyInWindow.get(outgoingChar) == 0) {
                    charFrequencyInWindow.remove(outgoingChar);
                }
                leftPointer++;
            }

            longestFound = Math.max(longestFound, rightPointer - leftPointer + 1);
        }

        return longestFound;
    }

    public static void main(String[] args) {
        String dnaSequence = "AABABCBCBAABC";
        int result = findLongest(dnaSequence, 2);
        System.out.println("DNA sequence: " + dnaSequence);
        System.out.println("Longest valid substring length (2 distinct): " + result);
    }
}

Recognising the Pattern Fast — The 3-Question Decision Framework

The hardest part of sliding window problems in an interview isn't the code — it's recognising within 60 seconds that sliding window is even the right tool. Interviewers watch this recognition moment closely.

Three questions will get you there every time. First: does the problem involve a contiguous subarray or substring? If the order doesn't matter or elements don't need to be adjacent, sliding window is the wrong tool — reach for a hash map or a sort instead. Second: is there a constraint on the window (sum ≥ target, at most k distinct, no repeating characters)? That constraint is what drives the window's expansion and contraction logic. Third: are you optimising for a minimum or maximum (shortest, longest, smallest, largest)? This tells you whether to update your answer after expanding (maximum) or after contracting (minimum).

For minimum problems — like smallest subarray with sum ≥ target — the trick is you shrink the window as aggressively as possible while still meeting the constraint, updating your best answer after each contraction, not after expansion.

package io.thecodeforge.algorithms;

public class MinSizeSubarraySum {

    /**
     * Finds the minimum length of a contiguous subarray whose sum is >= targetSum.
     * Time:  O(n)
     * Space: O(1)
     */
    public static int minSubarrayLength(int[] nums, int targetSum) {
        int leftPointer = 0, currentWindowSum = 0;
        int minimumLength = Integer.MAX_VALUE;

        for (int rightPointer = 0; rightPointer < nums.length; rightPointer++) {
            currentWindowSum += nums[rightPointer];

            // Update the answer INSIDE this loop — that's the minimum-problem pattern
            while (currentWindowSum >= targetSum) {
                minimumLength = Math.min(minimumLength, rightPointer - leftPointer + 1);
                currentWindowSum -= nums[leftPointer];
                leftPointer++;
            }
        }

        return (minimumLength == Integer.MAX_VALUE) ? 0 : minimumLength;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        int target = 7;
        System.out.println("Input: " + java.util.Arrays.toString(nums) + ", Target: " + target);
        System.out.println("Minimum length: " + minSubarrayLength(nums, target));
    }
}

Production-Grade Implementation: Handling Stream Data

In real-world systems, data often arrives as a stream rather than a static array. For these cases, we use specialized data structures or reactive patterns. Below is how you would model a sliding window over a potentially infinite stream of integers using a standard Java queue to represent the window state.

package io.thecodeforge.algorithms;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Simulates a sliding window over a stream of data.
 * This mimics how production systems track rolling averages or rate limits.
 */
public class StreamSlidingWindow {
    private final int windowSize;
    private final Queue<Integer> window = new LinkedList<>();
    private double runningSum = 0;

    public StreamSlidingWindow(int size) {
        this.windowSize = size;
    }

    public void addReading(int val) {
        window.add(val);
        runningSum += val;

        if (window.size() > windowSize) {
            runningSum -= window.poll();
        }
    }

    public double getRollingAverage() {
        return window.isEmpty() ? 0 : runningSum / window.size();
    }

    public static void main(String[] args) {
        StreamSlidingWindow throughputTracker = new StreamSlidingWindow(3);
        int[] streamData = {100, 200, 300, 400, 500};

        for (int data : streamData) {
            throughputTracker.addReading(data);
            System.out.println("Added: " + data + " | Current Rolling Avg: " + throughputTracker.getRollingAverage());
        }
    }
}

Sliding Window Variants and Space Complexity Considerations

Sliding window can be extended to handle more complex constraints. One common variant is the monotonic queue (deque) based sliding window for problems like sliding window maximum or minimum. Instead of storing all elements, you maintain a deque of indices with monotonically decreasing values — the front always holds the maximum of the current window. This adds O(k) space but keeps the sliding process O(n).

Another variant: sliding window with hashmap for pattern matching (e.g., find all anagrams in a string). Here the window size is fixed but you need to match character frequency exactly. Use a frequency map and a counter of matched characters to avoid rescanning.

Space complexity varies across patterns. Fixed-size numeric windows can be O(1) — just two integers for sum and max. Dynamic windows with character constraints need O(k) space for frequency map, where k is the number of distinct characters allowed. Monotonic queue windows need O(k) for the deque. Understanding these trade-offs is crucial for memory-constrained environments like embedded systems or real-time trading engines.

package io.thecodeforge.algorithms;

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

public class SlidingWindowMaximum {

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

        for (int i = 0; i < n; i++) {
            // Remove indices outside current window
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            // Maintain decreasing order: remove smaller values from back
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);

            // Record maximum when window is complete
            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[] maxes = maxSlidingWindow(nums, k);
        System.out.println("Sliding window maximums: " + java.util.Arrays.toString(maxes));
    }
}

When Not to Slide — The Anti-Pattern That Wastes Cycles

You're three rounds deep in an interview, palms sweaty, and the problem involves subarrays. Your brain screams "sliding window!" — and sometimes that instinct is wrong.

Sliding windows only work when the data has a linear, contiguous constraint. The moment you need non-contiguous elements, reordering, or global comparisons, the window breaks. I've watched junior devs waste forty-five minutes forcing a sliding window onto a knapsack variant. Painful.

The real signal is monotonicity — does shrinking the window from the left always preserve the viability of what's on the right? If not, you're fighting the data structure. Use prefix sums, two pointers from opposite ends, or a frequency map with reset logic.

Production lesson: we once tried a sliding window for detecting traffic anomalies across time zones. The window leaked non-contiguous events. Rewrote it with a buffer and index tracking. 300ms became 12ms.

// io.thecodeforge — interview tutorial

def is_valid_sliding_window(arr, condition):
    # If condition requires non-contiguous elements, bail.
    # Example: find subarray with sum = k using TWO elements anywhere
    # Sliding window fails because it assumes adjacency
    left = 0
    window_sum = 0
    for right in range(len(arr)):
        window_sum += arr[right]
        # Shrink from left if sum exceeds target
        while window_sum > condition and left <= right:
            window_sum -= arr[left]
            left += 1
        if window_sum == condition:
            return True
    return False

# Counterexample: arr = [3, 2, 7, 1], k = 10
# Sliding window misses 3 + 7 = 10 because they're not adjacent
arr = [3, 2, 7, 1]
k = 10
print(is_valid_sliding_window(arr, k))  # False — but real answer is True

Medium — Where Interviewers Separate the Real Engineers

Easy sliding window problems are warm-ups. Medium problems test whether you can adapt the window shape on the fly. The difference? Constraints that change per element, not per window.

Real pattern: longest substring with at most K distinct characters. Your window expands freely until it violates the distinct count. Then you shrink not by one, but until the violation clears. That's not a fixed increment — it's a state-based shrink.

Another classic: maximum consecutive ones with K flips. Here, the window tracks the count of zeroes. When zeroes exceed K, you move the left pointer until one zero exits the window. The insight? You're not flipping — you're counting. The window itself models the allowable flips.

Production analogy: rate-limiting a microservice endpoint. The window tracks request timestamps. When new request arrives, you drop timestamps older than 1 second. That's not a size window — it's a time-based dynamic window. Exact same logic as substring with K distinct, just with Unix millis instead of characters.

Don't memorize problem variations. Understand why the window moves. Then you can defend it under pressure.

// io.thecodeforge — interview tutorial

def longest_ones_with_flips(nums, k):
    left = 0
    zero_count = 0
    max_len = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zero_count += 1

        # Shrink until we're back under K flips
        while zero_count > k:
            if nums[left] == 0:
                zero_count -= 1
            left += 1

        # Current window is valid
        current_len = right - left + 1
        max_len = max(max_len, current_len)

    return max_len

nums = [1,1,0,0,1,1,1,0,1,1]
k = 2
print(f"Max consecutive ones with {k} flips: {longest_ones_with_flips(nums, k)}")

Sliding Window Template: Fixed vs Dynamic Size

The sliding window technique can be categorized into two main types: fixed-size windows and dynamic-size windows. Understanding the template for each is crucial for efficient problem-solving.

Fixed-Size Window Template: - Initialize a window of size k. - Compute the result for the first window. - Slide the window by one element: remove the leftmost element and add the new rightmost element. - Update the result based on the new window.

Example: Given an array and an integer k, find the maximum sum of any contiguous subarray of size k.

Dynamic-Size Window Template: - Use two pointers (left and right) to expand and contract the window. - Expand the right pointer until a condition is violated. - Contract the left pointer until the condition is satisfied again. - Track the optimal result during the process.

Example: Find the longest subarray with sum less than or equal to a target.

Key Differences: - Fixed windows maintain a constant size; dynamic windows adjust based on constraints. - Fixed windows often use a simple loop; dynamic windows require careful pointer management.

Choosing the right template depends on whether the window size is predetermined or variable based on a condition.

# Fixed-size window: maximum sum subarray of size k
def max_sum_fixed(arr, k):
    if len(arr) < k:
        return None
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

# Dynamic-size window: longest subarray with sum <= target
def longest_subarray_sum_le(arr, target):
    left = 0
    current_sum = 0
    max_length = 0
    for right in range(len(arr)):
        current_sum += arr[right]
        while current_sum > target:
            current_sum -= arr[left]
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length

Sliding Window with Deque: Maximum/Minimum in Window

When you need to track the maximum or minimum value in a sliding window efficiently, a deque (double-ended queue) is the perfect data structure. It allows O(1) access to the window's extremum and O(n) overall time.

How it works: - Maintain a deque that stores indices of array elements. - For each new element, remove indices from the back that correspond to smaller (for max) or larger (for min) values. - Remove indices from the front that are out of the current window. - The front of the deque always holds the index of the current maximum/minimum.

Example: Given an array and window size k, return an array of maximums for each window.

Algorithm: 1. Initialize an empty deque and result list. 2. For each index i in the array: - Remove indices from back while arr[deque[-1]] <= arr[i] (for max). - Append i to deque. - Remove front index if it's out of window (i - deque[0] >= k). - If i >= k-1, add arr[deque[0]] to result. 3. Return result.

This technique is essential for problems like "Sliding Window Maximum" on LeetCode.

Time Complexity: O(n) — each element is added and removed from deque at most once. Space Complexity: O(k) for the deque.

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()
    result = []
    for i, num in enumerate(nums):
        # Remove smaller elements from back
        while dq and nums[dq[-1]] <= num:
            dq.pop()
        dq.append(i)
        # Remove out-of-window indices from front
        if dq[0] <= i - k:
            dq.popleft()
        # Add to result when window is full
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

Sliding Window with Hash Map: Count Occurrences Pattern

When a problem involves counting occurrences of elements within a window (e.g., distinct characters, frequency of items), combining a sliding window with a hash map is a powerful pattern. The hash map stores the count of each element in the current window, enabling O(1) updates and lookups.

Common Use Cases: - Longest substring without repeating characters. - Find all anagrams in a string. - Minimum window substring.

Pattern Template: 1. Use two pointers (left, right) to define the window. 2. Maintain a hash map (or counter) for elements in the window. 3. Expand right pointer, updating the map. 4. When a condition is violated (e.g., duplicate found), shrink from left until condition is restored. 5. Track the optimal result (e.g., maximum length, minimum window).

Example: Longest Substring Without Repeating Characters - Use a hash map to store the last index of each character. - When a character repeats, move left pointer to max(left, last_index + 1). - Update the character's index and compute max length.

Time Complexity: O(n) — each element is visited at most twice. Space Complexity: O(min(m, n)) where m is the size of the character set.

This pattern is essential for string problems involving frequency constraints.

def length_of_longest_substring(s):
    char_map = {}
    left = 0
    max_len = 0
    for right, char in enumerate(s):
        if char in char_map and char_map[char] >= left:
            left = char_map[char] + 1
        char_map[char] = right
        max_len = max(max_len, right - left + 1)
    return max_len