Sliding Window Pattern — Solving Subarray Problems Efficiently
The Interview Question
What is the sliding window technique? When do you use a fixed vs. variable window?
Expert Answer
The sliding window technique maintains a 'window' (a contiguous subarray or substring) that slides across the input, updating the result as it moves. Instead of recalculating from scratch for every possible subarray (O(n²) or O(n³)), you add the new element entering the window and remove the element leaving — updating in O(1) per step for O(n) total. Fixed-size windows solve problems like 'maximum sum of k consecutive elements' — slide a window of size k across the array. Variable-size windows solve problems like 'longest substring without repeating characters' — expand the right boundary until a constraint is violated, then shrink the left boundary until it's valid again. The variable window pattern is more common in interviews and follows a template: expand right, check constraint, shrink left while invalid, update result.
Key Points to Hit in Your Answer
- Reduces O(n²) or O(n³) subarray problems to O(n)
- Fixed window: size is given (max sum of k elements)
- Variable window: size adapts to constraints (longest valid substring)
- Variable window template: expand right → check condition → shrink left → update answer
- Often combined with a hash map for character/element counting
- Classic problems: max sum subarray, longest substring without repeats, minimum window substring
Code Example
# Fixed window: max sum of k consecutive elements
def max_sum_k(nums, k):
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k] # slide: add right, remove left
max_sum = max(max_sum, window_sum)
return max_sum
# Variable window: longest substring without repeating chars
def longest_unique_substring(s):
char_index = {}
left = 0
max_length = 0
for right in range(len(s)):
if s[right] in char_index and char_index[s[right]] >= left:
left = char_index[s[right]] + 1 # shrink past duplicate
char_index[s[right]] = right
max_length = max(max_length, right - left + 1)
return max_length
# Variable window: minimum window containing all target chars
def min_window(s, t):
from collections import Counter
need = Counter(t)
missing = len(t)
left = 0
result = ""
for right, char in enumerate(s):
if need[char] > 0:
missing -= 1
need[char] -= 1
while missing == 0: # all chars found — try shrinking
window = s[left:right + 1]
if not result or len(window) < len(result):
result = window
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return resultWhat Interviewers Are Really Looking For
The variable window template (expand, check, shrink, update) is the framework they want to see. When you see 'longest/shortest subarray/substring with constraint X', sliding window should be your first instinct. For minimum window substring — one of the hardest medium problems — walking through the shrinking phase step by step shows strong problem-solving ability.
Practice This Question with AI Grading
Reading about interview questions is a start — but practicing with real-time AI feedback is how you actually get better. Goliath Prep grades your answers instantly and tells you exactly what you're missing.
Start Practicing Free →