Sliding Window

Sliding window is the pattern for contiguous ranges when recomputing from scratch would waste work. Instead of asking every possible range independently, you keep a live range and update its state as the range moves.

A Window Is a Range Plus State

A window has boundaries, usually left and right, and state such as sum, count, frequency map, max length, violation count, or current cost. The engineering advantage is incremental update: when the right side expands, add one item; when the left side shrinks, remove one item.

Scenario: API Rate Limit Window

A service allows 100 requests per user in any 60-second window. A naive implementation might scan all historical requests for every new request. A windowed design keeps only recent timestamps, removes expired ones, and checks the current count.

Variable Window in Java, Python, and JavaScript

The following function finds the longest subarray with sum at most a budget when values are non-negative. Non-negative values matter because expanding only increases the sum and shrinking only decreases it.

class LongestBudgetWindow {
    static int longestAtMost(int[] costs, int budget) {
        int left = 0;
        int sum = 0;
        int best = 0;
        for (int right = 0; right < costs.length; right++) {
            sum += costs[right];
            while (sum > budget) {
                sum -= costs[left];
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Fixed vs Variable Windows

Field judgmentEngineering Notes

• Define what makes the window valid.
• Define what state is maintained.
• Explain why each element enters and leaves at most once.
• For negative numbers, sum-window assumptions can fail.
• Tie window state to product constraints like time, budget, length, or uniqueness.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Return the length of the longest substring containing at most k distinct characters.
• Given non-negative costs, return the longest contiguous subarray with total cost at most budget.
• Allow a request only if the user has fewer than limit requests in the last 60 seconds.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

import java.util.*;

class LongestKDistinct {
    static int longest(String s, int k) {
        Map<Character, Integer> counts = new HashMap<>();
        int left = 0;
        int best = 0;

        for (int right = 0; right < s.length(); right++) {
            char add = s.charAt(right);
            counts.put(add, counts.getOrDefault(add, 0) + 1);

            while (counts.size() > k) {
                char remove = s.charAt(left++);
                counts.put(remove, counts.get(remove) - 1);
                if (counts.get(remove) == 0) counts.remove(remove);
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

class BudgetSubarray {
    static int longest(int[] costs, int budget) {
        int left = 0, sum = 0, best = 0;
        for (int right = 0; right < costs.length; right++) {
            sum += costs[right];
            while (sum > budget) {
                sum -= costs[left];
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

import java.util.*;

class RateLimiter {
    private final Map<String, Deque<Long>> byUser = new HashMap<>();

    boolean allow(String userId, long nowMs, int limit) {
        Deque<Long> window = byUser.computeIfAbsent(userId, _id -> new ArrayDeque<>());
        long cutoff = nowMs - 60_000;
        while (!window.isEmpty() && window.peekFirst() <= cutoff) {
            window.removeFirst();
        }
        if (window.size() >= limit) return false;
        window.addLast(nowMs);
        return true;
    }
}

Solved modelWorked Interview Answer

Find the longest contiguous subarray with sum at most a budget when all values are non-negative. Maintain a valid window. Non-negative values make shrinking safe because removing from the left cannot increase the sum.

class BudgetWindow {
    static int longestAtMost(int[] costs, int budget) {
        int left = 0, sum = 0, best = 0;
        for (int right = 0; right < costs.length; right++) {
            sum += costs[right];
            while (sum > budget) sum -= costs[left++];
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Using sliding window for non-contiguous selections.
• Forgetting to remove state when the left pointer moves.
• Applying sum-window logic with negative numbers without checking whether monotonic shrink still works.

Execution guardrailQuick-Start Checklist

• Define the window boundaries.
• Define the maintained state.
• Define when the window is valid.
• Shrink until valid.
• Record the answer at the correct time.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice longest substring without repeating characters.
• Study rate limiters and rolling metrics.
• Compare sliding window with prefix sums for range problems.