Sliding Window Technique — Fixed vs Variable, with Java Solutions

Sliding window maintains a contiguous range of elements and updates state incrementally as the window slides. Turns O(n·k) brute force into O(n).

Two flavors

Fixed-size window

• K is given
• Window size constant
• Add arr[right], remove arr[right - k]
• Track max/min/etc.

Variable-size window

• Two pointers left, right
• right expands, left contracts when condition violated
• Track longest/shortest/count of valid windows

Both are O(n)

• Each element enters and exits at most once
• Amortized linear

When to use

• Contiguous subarray or substring
• Optimization goal: longest, shortest, max sum, min sum, count, existence
• State is incrementally updatable (sum, count, frequency)

When not to use

• Non-contiguous (subsequence — use DP)
• Need reordering (use two pointers on sorted)
• State can't be updated incrementally (median — use two heaps)

Fixed-size template (max sum subarray of size K)

1. 1
   Compute sum of first K elements
2. 2
   For each new position: sum += arr[right] - arr[right - k]; update max
3. 3
   O(n), O(1) space

Variable-size template (longest substring without repeating)

1. 1
   Map<Character, Integer> lastSeen; left = 0, maxLen = 0
2. 2
   For each right: if char seen and within window, move left past it
3. 3
   Update lastSeen and maxLen

Generic variable template

• Expand right, update state
• While condition violated: shrink left, update state
• Update result

Common applications

Sum-based

• Max/min sum subarray of size K
• Smallest subarray with sum ≥ target
• Longest subarray with sum = K

Character-based

• Longest substring without repeating
• Longest substring with at most K distinct
• Longest substring with exactly K distinct (atMost(K) - atMost(K-1))
• Minimum window substring (classic hard)
• Anagrams / permutations in string

Deque-based

• Max in each window of size K (monotonic deque, O(n) amortized)

Key tricks

Frequency map for 'at most K distinct'

• count.merge(c, 1, Integer::sum)
• while count.size() > K: decrement/remove at left

ASCII vs Unicode

• int[128] or int[256] for ASCII (fast, cache-friendly)
• HashMap<Character, Integer> for Unicode

'Exactly K' trick

• Transform to 'at most K' minus 'at most K-1'
• Simplifies logic

Window size formula

• right - left + 1 (inclusive)
• Common off-by-one mistake

Common pitfalls

1. Nested loops instead of incremental update

• Wastes the technique — O(n·k) instead of O(n)

2. Off-by-one in window size

• size = right - left + 1
• Not right - left

3. Forgetting to shrink

• Window grows unbounded — wrong result

4. Integer overflow

• Products with large values — use long

5. Negative numbers

• Standard variable window assumes monotone behavior
• With negatives, window may need shrinking even when adding helps
• Use prefix sums + deque for mixed-sign subarray sum problems

6. Edge cases

• Empty input
• K > n (fixed-size impossible)
• K = 0

Recommendation: Sliding window is one of the most common patterns in coding interviews — master both the fixed and variable templates because they cover 80% of contiguous-range problems. Use fixed when the window size is explicitly given (max sum subarray of size K, anagrams); use variable when searching for the longest or shortest window satisfying a condition (longest without repeating, minimum window containing all chars of T). The key insight is incremental state maintenance: don't recompute — add what enters, remove what exits. This gives O(n) amortized even when the inner logic looks like a nested loop. For frequency tracking, prefer int[] over HashMap when the alphabet is ASCII (much faster, no hashing overhead). Use the 'atMost(K) - atMost(K-1)' trick for 'exactly K distinct' problems — it's cleaner than tracking exact-K directly. Watch for negative numbers in subarray-sum problems — standard variable window may fail; use prefix sums with a monotonic deque or HashMap. Always handle edge cases: empty input, K > n, K = 0. The mental model: window = contiguous range with state; move the window, update state, record result. Once you see a problem involving contiguous subarrays with an optimization goal, sliding window should be your first instinct.