Explain Sliding Window: Fixed-Size vs Variable-Size, Expand Right / Shrink Left

• Sliding window – a technique that maintains a contiguous range over an array or string using two indexes, updating a running result in O(n) instead of recomputing over every subrange.
• Fixed-size window – keeps a constant width K and slides one step at a time, adding the entering element and subtracting the leaving element.
• Variable-size window – grows the right edge in an outer loop and shrinks the left edge in an inner loop based on a condition.
• Amortized linear – even with the nested inner loop, each element enters and leaves the window exactly once, giving O(n) total work.
• Validity tracking – many problems use a frequency map or a counter to check window validity in O(1) per step.

What is the sliding window technique?

The sliding window technique maintains a contiguous range over an array or string using two indexes. Instead of recomputing an aggregate (like a sum, count, or frequency map) over every subrange from scratch, you update the aggregate incrementally by adding the element that enters the window and removing the element that leaves it. This turns O(n x K) or O(n^2) brute-force scans into a single O(n) pass.

package com.bank.service;

// Fixed-size window: rolling K-day sum of transactions
public class FixedWindowSum {
    public static int[] rollingSum(int[] txnAmounts, int k) {
        int n = txnAmounts.length;
        if (n < k) return new int[0];
        int[] result = new int[n - k + 1];
        int sum = 0;

        for (int i = 0; i < n; i++) {
            sum += txnAmounts[i];               // add entering element
            if (i >= k) sum -= txnAmounts[i - k]; // remove leaving element
            if (i >= k - 1) result[i - k + 1] = sum;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] daily = {1000, 2000, 1500, 3000, 2500};
        int[] sums = rollingSum(daily, 3);
        for (int s : sums) System.out.print(s + " ");
    }
}

4500 6500 7000

How does a fixed-size window work?

A fixed-size window of width K first builds the window over the first K elements, computing an initial aggregate. Then it slides: for each new right index, it adds the entering element and subtracts the element that just left the window at position right - K. The aggregate stays current in O(1) per step.

// Template for fixed-size window:
int sum = 0;
for (int i = 0; i < k; i++) sum += arr[i];  // build initial window
result[0] = sum;
for (int i = k; i < n; i++) {
    sum += arr[i];         // entering element
    sum -= arr[i - k];     // leaving element
    result[i - k + 1] = sum;
}

How does a variable-size window work?

A variable-size window uses an outer loop that advances the right edge to expand, and an inner while loop that advances the left edge to shrink whenever a condition is violated (for longest-valid) or still satisfied (for shortest-valid).

package com.bank.service;

// Variable window: longest span with sum at most a limit
public class VariableWindowLongest {
    public static int longestSpanUnderLimit(int[] txnAmounts, int limit) {
        int left = 0, best = 0;
        long sum = 0;
        for (int right = 0; right < txnAmounts.length; right++) {
            sum += txnAmounts[right];
            while (sum > limit) {
                sum -= txnAmounts[left];
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        int[] txns = {500, 200, 800, 300, 100, 700};
        int limit = 1200;
        System.out.println("Longest span under " + limit + ": " + longestSpanUnderLimit(txns, limit));
    }
}

Longest span under 1200: 3

How do longest-valid and shortest-valid windows differ?

For a longest-valid window, you shrink while the window is invalid, then record the current width. For a shortest-valid window, you shrink while the window is still valid, recording the minimum width each time it holds.

| Aspect | Longest-Valid | Shortest-Valid |
|---|---|---|
| Goal | Maximize window width | Minimize window width |
| Shrink condition | While invalid | While valid |
| Record answer | After restoring validity | Each time the window is valid |
| Example | Longest substring without repeating | Minimum window substring |

package com.bank.service;

// Shortest window with sum >= target
public class VariableWindowShortest {
    public static int shortestSpanOverTarget(int[] txnAmounts, int target) {
        int left = 0, best = Integer.MAX_VALUE;
        long sum = 0;
        for (int right = 0; right < txnAmounts.length; right++) {
            sum += txnAmounts[right];
            while (sum >= target) {
                best = Math.min(best, right - left + 1);
                sum -= txnAmounts[left];
                left++;
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }

    public static void main(String[] args) {
        int[] txns = {500, 200, 800, 300, 100, 700};
        int target = 1000;
        System.out.println("Shortest span over " + target + ": " + shortestSpanOverTarget(txns, target));
    }
}

Shortest span over 1000: 2

Why is the time amortized linear?

The inner while loop looks like it could make the algorithm quadratic, but it does not. The left pointer only ever moves forward. Each element enters the window once (when right advances over it) and leaves the window once (when left advances past it). The total number of left-pointer advances across the entire outer loop is bounded by n, so the total work is O(n).

// Amortized analysis:
// right advances n times (outer loop)
// left advances at most n times total (inner loop across all iterations)
// Total operations: 2n = O(n)

What data structures track window state?

Many sliding window problems carry a frequency map (HashMap or int array) or a counter to check window validity in O(1) per step. For example, longest substring without repeating characters uses a map of character positions. Minimum window substring uses a frequency map and a matched count.

package com.bank.service;

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

public class LongestSubstringNoRepeat {
    public static int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> lastSeen = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
                left = lastSeen.get(c) + 1;
            }
            lastSeen.put(c, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("TRANSFER")); // 8
        System.out.println(lengthOfLongestSubstring("ABCABC"));   // 3
    }
}

8
3

What are common mistakes?

The most common mistake is forgetting to advance the left pointer in the shrink loop, causing an infinite loop.

// WRONG: infinite loop
while (sum > limit) {
    sum -= arr[left];
    // Missing: left++;
}

// CORRECT:
while (sum > limit) {
    sum -= arr[left];
    left++;
}

Another mistake is confusing the shrink direction. For longest-valid, shrink while invalid. For shortest-valid, shrink while valid. Swapping the two gives wrong answers.

When should you use a sliding window?

Use a sliding window whenever the problem asks about a contiguous subrange of an array or string and the brute-force approach scans every subrange from scratch. Recognize the pattern by these signals: the words "contiguous," "subarray," "substring," a size constraint, or an optimization over a window.

// Pattern recognition checklist:
// 1. Is the input an array or string? Yes -> possible window
// 2. Does the problem involve a contiguous subrange? Yes -> likely window
// 3. Is the brute force O(n^2) or O(n*K)? Yes -> window reduces to O(n)
// 4. Fixed size given? -> fixed window
// 5. Optimize size subject to a constraint? -> variable window

What should a senior engineer know?

A senior engineer should recognize which variant a problem needs. Fixed-size applies when the window width is given. Variable-size applies when you optimize the width subject to a constraint, and the shrink condition flips between longest and shortest problems.

The amortized linear time is the whole reason the technique beats brute force. Each element enters and leaves exactly once despite the nested inner loop.

What are common interview follow-up questions?

• Interviewers commonly ask:
• What is the time complexity despite the nested loop? (O(n) amortized, left advances at most n times total.)
• Fixed or variable? (Fixed when width is given, variable when optimizing width.)
• How do you track validity? (HashMap, frequency array, or counter depending on the problem.)
• What if elements can be negative? (Variable window with positive-sum assumptions may break; may need prefix sums or a deque.)