This is the biggest shift in the entire sliding window series.
Every problem in Parts 1–4 had a fixed window size. You were always told: look at every subarray of size k. The window slid one step at a time — add one element, remove one element — like clockwork. The challenge was in what you tracked inside the window, not in the window itself.
In this post, there is no k. The window size is not given. Instead, the window expands and contracts dynamically, and finding the right size is the core of the problem.
How Variable-Size Windows Work
The structure uses two pointers — a left boundary and a right boundary — both starting at 0.
The right pointer always moves forward, one step per iteration of the outer loop. Every time it moves, the window expands by including the new element.
The left pointer only moves forward when needed. After expanding, if the window violates some condition (sum too large, too many zeros, product exceeds a limit), we shrink from the left — advancing the left pointer and removing elements — until the condition is restored.
Here’s the template:
left = 0
for right = 0 to n-1:
expand window by including nums[right]
while (window violates condition):
shrink window by excluding nums[left]
left++
evaluate window (update answer)Why This Is Still O(n)
The nested while loop looks like it could make this O(n²), but it doesn’t. The key observation is that the left pointer never moves backward. Across the entire execution, left moves from 0 to at most n. The right pointer also moves from 0 to n. So the total number of pointer movements is at most 2n, which is O(n).
Each element is added to the window exactly once (when right passes it) and removed at most once (when left passes it). No element is processed more than twice.
Fixed vs. Variable: What Changes
| Fixed-Size (Parts 1–4) | Variable-Size (Part 5) | |
|---|---|---|
| Window size | Given as k | Unknown — the answer itself |
| Right pointer | Moves one step per iteration | Same |
| Left pointer | Always at right – k + 1 | Moves forward only when condition violated |
| Shrink trigger | Automatic (window exceeds k) | Conditional (while loop) |
| Core question | “What’s inside this window?” | “What’s the best window size?” |
The Reframing Challenge
Some variable-size problems are straightforward — the problem directly asks for “the shortest subarray with sum >= target” and you can see the two-pointer approach immediately.
But others disguise the sliding window. The problem might talk about removing elements from both ends, or flipping zeros, or counting valid subarrays. Before you can apply the template, you need to reframe the problem into “find a contiguous subarray that satisfies condition X.” This reframing step is often the hardest part.
Problem 12: Minimum Size Subarray Sum (LC 209)
Difficulty: Medium
Problem: Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If no such subarray exists, return 0.
Why variable-size: There’s no fixed k. Different regions of the array might need different window sizes to reach the target. The optimal answer could be 1 (a single large element) or the entire array.
Key Insight: Since all numbers are positive, adding an element always increases the sum and removing one always decreases it. This monotonic behavior is what makes the two-pointer approach correct — once the sum reaches the target, shrinking from the left can only make it smaller, so we don’t miss any valid windows.
Solution (C++)
cpp
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int startIdx = 0;
int sumSoFar = 0;
int minLen = INT_MAX;
for (size_t i = 0; i < nums.size(); ++i) {
sumSoFar += nums[i];
while (sumSoFar >= target) {
minLen = min(minLen, (int)i - startIdx + 1);
sumSoFar -= nums[startIdx++];
}
}
return minLen == INT_MAX ? 0 : minLen;
}
};How the Window Moves
The outer loop expands by adding nums[i] to sumSoFar. Once sumSoFar >= target, the while loop kicks in: record the current window length, subtract the leftmost element, and advance startIdx. This continues until the sum drops below the target.
At each position of the right pointer, we find the tightest valid window ending there. The overall minimum across all positions is the answer.
Notice minLen starts at INT_MAX as a sentinel. If it’s never updated, no valid subarray exists.
Time: O(n) Space: O(1)
Problem 13: Subarray Product Less Than K (LC 713)
Difficulty: Medium
Problem: Given an array of positive integers nums and an integer k, return the number of contiguous subarrays where the product of all elements is strictly less than k.
Why variable-size: The valid window size depends on the product of elements, which varies across the array. A subarray of length 5 might be valid in one region but not another.
Key Insight: The structure is identical to LC 209 — expand by multiplying, shrink by dividing — but with a clever counting twist.
The Counting Trick
At each position i, the window from idx to i is the longest subarray ending at i whose product is less than k. How many valid subarrays end at position i? Exactly i – idx + 1. These are the subarrays [idx..i], [idx+1..i], [idx+2..i], all the way down to [i..i]. Since the full window is valid and all numbers are positive (so shorter subarrays have smaller products), every sub-window is also valid.
By summing i – idx + 1 at each position, we count every valid subarray exactly once without double-counting.
Solution (C++)
cpp
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if (k <= 1) {
return 0;
}
int numArrs = 0;
long long productSoFar = 1;
int idx = 0;
for (size_t i = 0; i < nums.size(); ++i) {
productSoFar *= nums[i];
while (productSoFar >= k) {
productSoFar /= nums[idx++];
}
numArrs += i - idx + 1;
}
return numArrs;
}
};Comparing to LC 209
The mechanics are almost identical. The differences:
- Arithmetic is multiply/divide instead of add/subtract
- We shrink when the product is too large (>= k), keeping the window valid
- Instead of tracking minimum length, we count subarrays using the i – idx + 1 formula
- The edge case guard (k <= 1) handles the fact that all elements are at least 1, so no product can be less than 1
Time: O(n) Space: O(1)
Problem 14: Minimum Operations to Reduce X to Zero (LC 1658)
Difficulty: Medium
Problem: Given an integer array nums and an integer x, you can remove the leftmost or rightmost element and subtract its value from x. Return the minimum number of operations to reduce x to exactly 0, or -1 if impossible.
Why this is a sliding window problem (the reframing):
At first glance, this doesn’t look like sliding window at all. You’re removing from both ends, not looking at a contiguous subarray.
Here’s the trick: flip the problem. If you remove some elements from the left and right that sum to x, the remaining elements in the middle form a contiguous subarray. That middle subarray’s sum must equal totalSum – x.
Minimizing the number of removed elements is the same as maximizing the length of the middle subarray whose sum equals totalSum – x.
Now it’s a standard variable-size sliding window: find the longest subarray with a specific target sum.
Solution (C++)
cpp
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int target = accumulate(nums.begin(), nums.end(), 0) - x;
int idx = 0;
int sumSoFar = 0;
int maxLen = -1;
for (size_t i = 0; i < nums.size(); ++i) {
sumSoFar += nums[i];
while (idx <= i && sumSoFar > target) {
sumSoFar -= nums[idx++];
}
if (sumSoFar == target) {
maxLen = max(maxLen, (int)i - idx + 1);
}
}
return maxLen == -1 ? -1 : nums.size() - maxLen;
}
};Why the Reframing Works
The original problem: pick elements from the left and right edges that sum to x, using the fewest picks. The reframed problem: find the longest contiguous middle section that sums to totalSum – x. They’re complements — whatever you don’t remove stays in the middle, and whatever stays in the middle you don’t remove.
The answer converts back at the end: nums.size() – maxLen gives the number of removed elements.
This is the most important lesson from this problem. The sliding window technique was always the right approach — the hard part was seeing past the original framing.
Time: O(n) Space: O(1)
Problem 15: Max Consecutive Ones III (LC 1004)
Difficulty: Medium
Problem: Given a binary array nums and an integer k, return the maximum number of consecutive 1’s in the array if you can flip at most k 0’s.
The reframing: Don’t think about flipping zeros. Think about it as: find the longest subarray that contains at most k zeros. Every zero in the window represents one flip. The window length (including both 1’s and flipped 0’s) is the answer.
This reframing turns a “manipulation” problem into a clean variable-size sliding window.
Solution (C++)
cpp
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int longest = 0;
int numFlipped = 0;
int idx = 0;
for (int i = 0; i < nums.size(); ++i) {
numFlipped += nums[i] == 0 ? 1 : 0;
while (idx <= i && numFlipped > k) {
numFlipped -= nums[idx++] == 0 ? 1 : 0;
}
longest = max(longest, i - idx + 1);
}
return longest;
}
};How the Window Moves
As the right pointer advances, count zeros via numFlipped. When numFlipped exceeds k, shrink from the left: if the element being removed is a 0, decrement numFlipped. Keep shrinking until numFlipped is back to k or less.
At each step, i – idx + 1 is the window length — the number of consecutive 1’s achievable if we apply all k flips within this window. Track the maximum.
We never need to track 1’s explicitly. The window length minus the zero count gives us the 1’s count, but we don’t even need that — the window length itself is the answer.
Time: O(n) Space: O(1)
The Variable-Size Template Across All Four Problems
Every problem follows the same skeleton:
left = 0
state = initial value
for right = 0 to n-1:
update state with nums[right] // expand
while (state violates condition):
update state removing nums[left] // shrink
left++
update answer with current window // evaluateWhat varies:
| Problem | State | Condition to Shrink | Answer |
|---|---|---|---|
| Min Size Sum (209) | Running sum | sum >= target | Minimum window length |
| Product < K (713) | Running product | product >= k | Count of valid subarrays |
| Reduce X to Zero (1658) | Running sum | sum > target | Maximum window length (then convert) |
| Max Ones III (1004) | Count of 0’s | zeros > k | Maximum window length |
Full Series Recap: Parts 1–5
Across 15 problems and 5 posts, we’ve covered the complete sliding window spectrum:
Part 1 (Basic Fixed Window): LC 346, 643, 1343 — Running sum, one-line evaluation changes. The mechanical foundation.
Part 2 (Conditional Fixed Window): LC 1176, 1052, 1456, 1100 — Same mechanics, but richer state: multi-branch scoring, dual counters, vowel sets, hash maps for uniqueness.
Part 3 (Monotonic Deque): LC 239 — Fixed window, but maintaining the max requires a new data structure. Introduction to the idea that the window’s internal state can be non-trivial.
Part 4 (Complex State): LC 567, 438, 480 — Fixed window with frequency maps and balanced BSTs. The template is unchanged; the data structure work per step gets heavier.
Part 5 (Variable-Size): LC 209, 713, 1658, 1004 — No fixed k. The window grows and shrinks based on conditions. Some problems require reframing before the sliding window is even visible.
The single most important skill across all these problems is decomposition: identify what the window tracks, when it should grow or shrink, and how to evaluate it. Once you answer those three questions, the code follows a predictable template — whether the window holds a single integer or two balanced BSTs, whether it’s fixed at size k or dynamically adapting to the data.
Thanks for following along with the full series! If you’re preparing for interviews, practice identifying these patterns before jumping into code — recognition is half the battle.
