BeginnerPython · 25 min

Sliding Window: Beginner

Here is the single most important thing to understand about sliding window problems: the interviewer is testing whether you think incrementally. The brute-force solution recomputes the sum (or max, or set, or count) for every possible window from scratch. The sliding window solution computes it once, then updates it by adding what enters and removing what leaves. That mental shift, from 'recompute everything' to 'update the delta,' is the exact same shift that separates a junior data engineer who rebuilds entire tables from a senior one who processes incrementally. The interviewer knows this, and that is why they ask the question.

What you will be able to do

Recognize the five keywords that signal a sliding window problem

Implement fixed-width windows with the add-subtract trick

Maintain window state (sums, sets, counters) correctly

Connect sliding windows to rolling aggregations in real pipelines

Spotting the Pattern

Daily Life

Interviews

Recognize sliding window problems instantly

You are looking at a sliding window problem when you see:

▸"contiguous subarray" or "consecutive elements" (NOT subsequence)
▸"window of size K" or "K consecutive"
▸"rolling average" or "rolling sum"
▸"longest substring" or "shortest subarray"
▸"at most K distinct" or "sum less than target"
▸Any problem where brute force involves nested loops over subarrays

The distinction between sliding window and other patterns comes down to one word: contiguous. If the problem asks about a contiguous subarray or substring, sliding window is on the table. If it asks about a subsequence (elements do not need to be adjacent), sliding window is the wrong tool. This is the most common misidentification. Candidates try to slide a window on a subsequence problem and waste 15 minutes before realizing the approach does not work. Read the problem statement carefully. 'Subarray' and 'substring' mean contiguous. 'Subsequence' does not.

The second signal is a constraint on the window. 'Find the maximum sum of K consecutive elements.' 'Find the longest substring with at most K distinct characters.' 'Find the shortest subarray with sum >= target.' The constraint defines the window shape: fixed-width (K elements) or variable-width (expand until constraint violated). Fixed-width is the beginner version. Variable-width is intermediate. Both use the same expand-contract framework, but variable-width requires more state management.

The Incremental Thinking Test

Here is what the interviewer is really evaluating. When you see 'maximum sum of K consecutive elements,' do you immediately think 'I can compute the first window's sum, then slide: add the new element, subtract the leaving element'? Or do you reach for a nested loop that sums each window from scratch? The first approach is O(n). The second is O(n*K). The interviewer is testing whether incremental computation is your default mode of thinking. For data engineers, this is the difference between full-refresh ETL (recompute everything) and incremental ETL (process only what changed). The window problem is a microcosm of that mindset.

Say this in the interview: 'Instead of recomputing the sum for each window, I can maintain a running sum and update it by adding the new element and subtracting the one that just left the window. This gives me O(n) time instead of O(n*K).' That one sentence demonstrates incremental thinking, complexity awareness, and clear communication. It is the kind of opening that makes interviewers write 'strong pattern recognition' on the scorecard before you have even started coding.

✗Brute Force O(n*K)

Sum each window from scratch
Inner loop of K additions per window
Recomputes shared elements
Same as full-refresh ETL

✓Sliding Window O(n)

Compute first window, then slide
One addition + one subtraction per slide
Reuses computation from previous window
Same as incremental ETL

TIP

When the interviewer says 'contiguous subarray,' your inner voice should immediately say 'sliding window.' When they say 'K consecutive,' your inner voice should say 'fixed-width sliding window.' Train this pattern recognition until it is reflexive. In the interview, you do not have time to deliberate. You need to recognize and name the pattern in under 10 seconds.

Fixed-Width Windows: The Add-Subtract Trick

Daily Life

Interviews

Implement fixed-width windows with add-subtract

Fixed-width sliding windows are the simplest form. The window is always exactly K elements wide. As the window slides one position right, one element enters on the right and one element leaves on the left. The window state (sum, count, product) is updated by adding the entering element and subtracting the leaving element. No inner loop needed. One pass through the array.

Maximum Sum of K Consecutive Elements

This is the canonical beginner sliding window problem and the most frequently asked warm-up in data engineering phone screens. Given an array and integer K, find the maximum sum among all contiguous subarrays of length K. The brute force sums each window independently: O(n*K). The sliding window computes the first window's sum, then slides.

	def max_sum_k(arr, k):
	if len(arr) < k:
	return 0 # edge case: array smaller than window

	# Compute first window
	window_sum = sum(arr[:k])
	best = window_sum

	# Slide: add entering element, subtract leaving element
	for i in range(k, len(arr)):
	window_sum += arr[i] - arr[i - k]
	best = max(best, window_sum)

	return best

Walk through this with arr = [2, 1, 5, 1, 3, 2], K = 3. First window: [2, 1, 5], sum = 8. Slide: add 1, subtract 2 -> sum = 7. Slide: add 3, subtract 1 -> sum = 9. Slide: add 2, subtract 5 -> sum = 6. Maximum is 9 (window [5, 1, 3]). Four steps instead of twelve additions. On an array of 1 million elements with K = 1000, that is 1 million operations instead of 1 billion. The O(n) vs O(n*K) difference is not theoretical. It is the difference between a pipeline stage that finishes in seconds and one that takes hours.

Maximum Average Subarray (LeetCode 643)

Same problem, but return the average instead of the sum. Since average = sum / K and K is constant, maximizing the sum also maximizes the average. The code is identical; just divide by K at the end. This is a common phone screen question. You should solve it in under 5 minutes.

	def max_average(nums, k):
	window_sum = sum(nums[:k])
	best = window_sum
	for i in range(k, len(nums)):
	window_sum += nums[i] - nums[i - k]
	best = max(best, window_sum)
	return best / k

Edge Cases to Name Before Coding

Edge Case	What Happens	How to Handle
K > len(arr)	Cannot form a window	Return 0 or raise ValueError immediately
K = len(arr)	Only one window: the entire array	Return sum of entire array
All negative numbers	Maximum sum is the least negative window	Algorithm works unchanged
K = 1	Each element is its own window	Returns max(arr), which is correct

Name these edge cases BEFORE writing code. Say: 'First, let me handle edge cases. If K is larger than the array, there is no valid window. If K equals the array length, there is exactly one window.' The interviewer has a rubric item for proactive edge case handling. Naming them first is a 4/4 signal.

Window State: Beyond Sums

Daily Life

Interviews

Maintain window state correctly

Sums are the simplest window state. But many sliding window problems require richer state: a set of elements in the window, a frequency counter, a running product, or a boolean condition. The principle is the same: update the state incrementally as elements enter and leave. But the update logic gets more interesting.

Window with a Set: Contains Duplicate II (LeetCode 219)

Given an array, determine if there are two distinct indices i and j such that arr[i] == arr[j] and |i - j| <= K. Translation: is there a duplicate within any window of size K+1? Maintain a set of elements in the current window. When a new element enters, check if it is already in the set (duplicate found). Then remove the element that is leaving the window.

	def contains_duplicate_nearby(nums, k):
	window = set()
	for i, num in enumerate(nums):
	if num in window:
	return True
	window.add(num)
	# Remove element leaving the window
	if len(window) > k:
	window.remove(nums[i - k])
	return False

The state is a set, not a sum. The 'add' operation is window.add(). The 'subtract' operation is window.remove(). The constraint check is 'num in window.' The set maintains exactly the elements within the window of size K+1. Each add and remove is O(1) amortized. Total time: O(n). Total space: O(K).

Window with a Counter: Maximum of All Subarrays

When the window state is a frequency counter (Counter or defaultdict(int)), adding an element means incrementing its count. Removing means decrementing. If the count reaches zero, delete the key to keep the counter clean. This matters when the problem asks 'how many distinct elements in the window' because a counter with zero-value keys gives a wrong len().

	from collections import defaultdict

	def distinct_count_windows(arr, k):
	"""Count distinct elements in each window of size K."""
	counter = defaultdict(int)
	result = []

	for i in range(len(arr)):
	counter[arr[i]] += 1 # element enters

	if i >= k:
	leaving = arr[i - k]
	counter[leaving] -= 1
	if counter[leaving] == 0:
	del counter[leaving] # CRITICAL: remove zero-count keys

	if i >= k - 1:
	result.append(len(counter)) # distinct count in this window

	return result

The del counter[leaving] line is where most candidates introduce bugs. If you decrement to zero but do not delete the key, len(counter) still counts it as a distinct element even though it is no longer in the window. This is the sliding window equivalent of a data pipeline that does not clean up stale state. In production, stale state causes phantom records. In interviews, it causes wrong answers. Both are the same discipline: clean up after yourself.

Window with a Product

Some problems use multiplicative state instead of additive. The product of all elements in a window of size K. Entering: multiply by the new element. Leaving: divide by the departing element. Works perfectly unless a zero enters the window, at which point the product becomes zero and you cannot divide to recover. Handle the zero case by resetting the window.

✓Do

Delete counter keys when they reach zero count
Use a set for 'contains' checks, a counter for frequency
Handle the 'window not yet full' phase (i < k) explicitly
State the window state type before coding: 'I will maintain a set/counter/sum'

✗Don't

Leave zero-count keys in your counter (corrupts distinct counts)
Use 'if' instead of 'while' for variable-width contraction
Forget to remove the leaving element when the window slides
Reset the left pointer to 0 (destroys O(n) guarantee)

TIP

Before you start coding any sliding window problem, say: 'The window state I need is a [sum / set / counter / deque]. When an element enters, I [add / insert / increment]. When an element leaves, I [subtract / remove / decrement / delete if zero].' This 10-second plan prevents the most common bugs.

The Expand-Contract Framework

Daily Life

Interviews

Apply the expand-contract framework

Every sliding window problem, fixed or variable width, follows the same three-step loop: expand, contract, record. The right pointer expands the window by adding an element. The left pointer contracts the window by removing elements until the constraint is satisfied. Then you record the current window as a potential answer. This expand-contract-record rhythm is the template. Memorize it. Every sliding window problem is a variation of this template.

The Universal Template

	def sliding_window_template(arr, constraint):
	left = 0
	state = initial_state() # sum, set, counter, etc.
	best = initial_best() # 0 for max, inf for min

	for right in range(len(arr)):
	# 1. EXPAND: add arr[right] to window state
	add_to_state(state, arr[right])

	# 2. CONTRACT: shrink until constraint is met
	while not valid(state, constraint):
	remove_from_state(state, arr[left])
	left += 1

	# 3. RECORD: update best answer
	best = update_best(best, right - left + 1)

	return best

For fixed-width windows, step 2 simplifies to: if the window is larger than K, remove the leftmost element and advance left. No while loop needed because the window can only be one element too large. For variable-width windows, step 2 uses a while loop because the window might need to shrink by multiple elements before the constraint is restored.

The O(n) guarantee comes from the fact that each element is added exactly once (when right passes it) and removed at most once (when left passes it). The while loop in step 2 does not make it O(n^2) because left only moves forward. Across the entire execution, left moves at most n times total. So the total work across all iterations is at most 2n = O(n). This amortized analysis is what the interviewer expects you to state.

Fixed-Width vs Variable-Width

✓Fixed-Width (Size K)

Window always has exactly K elements
Contract is simple: if window > K, remove left
No while loop needed for contraction
Examples: max sum of K elements, rolling average

✓Variable-Width (Constraint-Based)

Window grows and shrinks based on constraint
Contract uses while loop: shrink until valid
State is more complex (set, counter, map)
Examples: longest substring, shortest subarray

The template works for both. The only difference is the contract step: fixed-width uses a simple if check, variable-width uses a while loop. Everything else is identical. When you see a new sliding window problem, plug it into the template: what is the state? What is the constraint? What is the 'best' metric (longest? shortest? maximum sum?)? Answer these three questions and the solution writes itself.

StateConstraintObjective

State

What does the window track?

Sum, count, frequency map, set, product, min/max. Define this before coding. It determines your add/remove operations.

Constraint

When is the window valid?

Size <= K, distinct count <= K, sum >= target. This determines your contract condition.

Objective

What are you optimizing?

Maximum length? Minimum length? Maximum sum? This determines your record operation.

The three-question framework (state, constraint, objective) is the fastest way to decompose any sliding window problem. Say it out loud: 'The state is a frequency counter. The constraint is at most K distinct characters. The objective is the maximum window length.' Three sentences, and the structure of your solution is clear.

Sliding Windows in Data Pipelines

Daily Life

Interviews

Connect sliding windows to real pipeline patterns

Here is where you turn a coding answer into a data engineering answer. Sliding windows are not just LeetCode problems. They are the foundation of rolling aggregations, session analysis, anomaly detection, and rate limiting in production data systems. Every time you write AVG(revenue) OVER (ORDER BY date ROWS BETWEEN 6 PRECEDING AND CURRENT ROW) in SQL, you are using a fixed-width sliding window. When you use Flink's SlidingEventTimeWindows, you are using the same algorithm. Connecting the interview problem to these real systems is what makes the interviewer write 'strong DE judgment' on the scorecard.

Rolling Aggregations

The most direct application. Computing a 7-day rolling average of daily revenue. A 30-day rolling user count. A 1-hour rolling error rate. All are fixed-width sliding windows over time-series data. In SQL, the ROWS BETWEEN clause handles this. In Python (when SQL is not available or the logic is too complex for SQL), you implement the same add-subtract trick.

	def rolling_average(values, timestamps, window_days=7):
	"""Compute rolling average over a time-based window."""
	from collections import deque
	window = deque() # (timestamp, value) pairs
	window_sum = 0
	results = []

	for ts, val in zip(timestamps, values):
	window.append((ts, val))
	window_sum += val
	# Remove elements outside the time window
	while window and (ts - window[0][0]).days > window_days:
	_, old_val = window.popleft()
	window_sum -= old_val
	results.append(window_sum / len(window))

	return results

Notice this is a TIME-BASED window, not an index-based window. The window size is 7 days, not 7 elements. Elements enter when they arrive and leave when they age out. This is exactly how Flink's time windows work. The deque maintains the window in arrival order, and the while loop evicts elements whose timestamp is too old. The sum is maintained incrementally. No inner loop to recompute.

Rate Limiting

A sliding window rate limiter allows at most N requests in the last T seconds. The window contains timestamps of recent requests. On each new request, evict timestamps older than T seconds, then check if the window has room. This is the same expand-contract pattern: expand by adding the new timestamp, contract by removing expired ones, check the constraint (window size < N).

	from collections import deque
	import time

	class RateLimiter:
	def __init__(self, max_requests, window_seconds):
	self.max_requests = max_requests
	self.window_seconds = window_seconds
	self.timestamps = deque()

	def allow(self):
	now = time.time()
	# Contract: remove expired timestamps
	while self.timestamps and now - self.timestamps[0] > self.window_seconds:
	self.timestamps.popleft()
	# Check constraint
	if len(self.timestamps) < self.max_requests:
	self.timestamps.append(now) # Expand
	return True
	return False

This is production-grade code. API gateways, Kafka consumer throttling, and pipeline backpressure mechanisms all use this exact pattern. When you solve a sliding window problem in an interview and then say 'this is the same algorithm I use for rate limiting in my pipelines,' you have just connected the dots that most candidates never connect.

Session Windowing

Session windows are variable-width windows where the boundary is a gap in events. A session ends when no event arrives for T minutes. In Flink, this is SessionWindows.withGap(Time.minutes(30)). In Python, you implement it by tracking the gap between consecutive events and starting a new session when the gap exceeds T. This is the LAG + cumulative SUM pattern you saw in the SQL Interview Patterns lesson, implemented as a sliding window.

The four DE applications to mention after solving any sliding window problem:

▸Rolling aggregations: 7-day revenue, 30-day retention, 1-hour error rate
▸Rate limiting: allow at most N requests per T seconds
▸Session windowing: group events into sessions based on inactivity gaps
▸Anomaly detection: flag values outside 3 standard deviations of the rolling mean

TIP

After solving any sliding window problem, take 15 seconds: 'In production, I use this pattern for rolling aggregations in my data quality monitors. The window tracks the trailing 7-day row count, and if today's count drops below 70% of the window average, it triggers an alert.' That one sentence turns a coding answer into a data engineering answer.

❯❯❯PUTTING IT ALL TOGETHER

> You are in a phone screen. The interviewer asks: 'Given an array of integers and an integer K, find the contiguous subarray of length K with the maximum average.'

You say: 'This is a fixed-width sliding window. I compute the sum of the first K elements, then slide: add the entering element, subtract the leaving element. O(n) time, O(1) space.'

You write clean code in 3 minutes. You handle the edge case where K > len(arr). You walk through a 6-element example.

You bridge: 'This is the same algorithm behind SQL rolling averages: AVG(x) OVER (ROWS BETWEEN K-1 PRECEDING AND CURRENT ROW). In my pipelines, I use this for 7-day rolling revenue and anomaly detection on row counts.'

KEY TAKEAWAYS

Contiguous + constraint = sliding window: if the problem says subarray (not subsequence) with a constraint, reach for a window

Add-subtract trick: compute once, update incrementally. O(n) instead of O(n*K).

State determines the operations: sum uses +/-, set uses add/remove, counter uses increment/decrement+delete

Expand-contract-record: the universal template for every sliding window problem

DE connections: rolling aggregations, rate limiting, session windows, anomaly detection

Stop recomputing everything. Slide the window, update the delta.

Category: Python
Difficulty: beginner
Duration: 25 minutes
Challenges: 0 hands-on challenges

Topics covered: Spotting the Pattern, Fixed-Width Windows: The Add-Subtract Trick, Window State: Beyond Sums, The Expand-Contract Framework, Sliding Windows in Data Pipelines

Lesson Sections

Spotting the Pattern (concepts: pySlidingWindow, pyPatternRecognition)
The distinction between sliding window and other patterns comes down to one word: contiguous. If the problem asks about a contiguous subarray or substring, sliding window is on the table. If it asks about a subsequence (elements do not need to be adjacent), sliding window is the wrong tool. This is the most common misidentification. Candidates try to slide a window on a subsequence problem and waste 15 minutes before realizing the approach does not work. Read the problem statement carefully. 'Su
Fixed-Width Windows: The Add-Subtract Trick (concepts: pyFixedWindow, pyWindowSum)
Fixed-width sliding windows are the simplest form. The window is always exactly K elements wide. As the window slides one position right, one element enters on the right and one element leaves on the left. The window state (sum, count, product) is updated by adding the entering element and subtracting the leaving element. No inner loop needed. One pass through the array. Maximum Sum of K Consecutive Elements This is the canonical beginner sliding window problem and the most frequently asked warm
Window State: Beyond Sums (concepts: pyWindowState, pyWindowSet, pyWindowCounter)
Sums are the simplest window state. But many sliding window problems require richer state: a set of elements in the window, a frequency counter, a running product, or a boolean condition. The principle is the same: update the state incrementally as elements enter and leave. But the update logic gets more interesting. Window with a Set: Contains Duplicate II (LeetCode 219) Given an array, determine if there are two distinct indices i and j such that arr[i] == arr[j] and |i - j| <= K. Translation:
The Expand-Contract Framework (concepts: pyExpandContract, pyWindowTemplate)
Every sliding window problem, fixed or variable width, follows the same three-step loop: expand, contract, record. The right pointer expands the window by adding an element. The left pointer contracts the window by removing elements until the constraint is satisfied. Then you record the current window as a potential answer. This expand-contract-record rhythm is the template. Memorize it. Every sliding window problem is a variation of this template. The Universal Template For fixed-width windows,
Sliding Windows in Data Pipelines (concepts: pyRollingAgg, pyRateLimiter, pySessionWindow)
Here is where you turn a coding answer into a data engineering answer. Sliding windows are not just LeetCode problems. They are the foundation of rolling aggregations, session analysis, anomaly detection, and rate limiting in production data systems. Every time you write AVG(revenue) OVER (ORDER BY date ROWS BETWEEN 6 PRECEDING AND CURRENT ROW) in SQL, you are using a fixed-width sliding window. When you use Flink's SlidingEventTimeWindows, you are using the same algorithm. Connecting the interv