Variable Size Sliding Window - Complete Guide for Interview

Overview

This is Part 2 of our Sliding Window series. If you haven’t read Part 1, check out Fixed Size Sliding Window first.

The Variable Size Sliding Window (also called Two Pointers) is one of the most frequently tested patterns in coding interviews. Unlike fixed-size windows, the window dynamically expands and shrinks based on certain conditions.

---

Fixed vs Variable Window

Aspect	Fixed Size	Variable Size
Window Size	Constant k	Dynamically changes
Pointers	One pointer (i)	Two pointers (left, right)
Shrink Condition	Always shrink by 1	Shrink while condition holds
Use Case	”Every window of size k"	"Longest/shortest subarray with…”

Fixed Window (size k=3):
[a b c] d e f → a [b c d] e f → a b [c d e] f → a b c [d e f]
  ↑                ↑                ↑                ↑
  Always size 3

Variable Window:
[a] b c d → [a b] c d → [a b c] d → a [b c] d → a [b c d]
↑           ↑           ↑           ↑           ↑
Expands and shrinks based on validity

---

Two Core Patterns

Variable sliding window problems fall into two categories:

Pattern 1: Find LONGEST Valid Subarray

• Goal: Maximize window size while keeping it valid
• Logic: Expand right, shrink left when invalid
• Update: After shrinking (window is valid)

Pattern 2: Find SHORTEST Valid Subarray

• Goal: Minimize window size while keeping it valid
• Logic: Expand right until valid, then shrink as much as possible
• Update: Inside the while loop (while valid)

---

Problem 1: Max Consecutive Ones II (LC 487)

Description: Given a binary array nums, return the maximum number of consecutive 1s in the array if you can flip at most one 0.

Example:

• Input: nums = [1, 0, 1, 1, 0]
• Output: 4
• Explanation: Flip the first zero to get [1, 1, 1, 1, 0], which has 4 consecutive ones.

Approach

This is a “Find Longest” problem. We maintain a window that contains at most one zero.

nums = [1, 0, 1, 1, 0]

Step 1: [1]           → 0 zeros, valid, len=1
Step 2: [1, 0]        → 1 zero, valid, len=2
Step 3: [1, 0, 1]     → 1 zero, valid, len=3
Step 4: [1, 0, 1, 1]  → 1 zero, valid, len=4 ✓
Step 5: [1, 0, 1, 1, 0] → 2 zeros, INVALID!
        Shrink: [0, 1, 1, 0] → still 2 zeros
        Shrink: [1, 1, 0] → 1 zero, valid, len=3
        
Result: 4

Interactive Visualization

Watch how the window expands with right pointer and shrinks with left pointer when the zero count exceeds the limit:

Key Observations:

• Green (1s): Valid elements in our window
• Red (0s): Zeros we’re “flipping” - we can have at most k of these
• L pointer: Shrinks window when invalid
• R pointer: Always expands to explore new elements

JavaPythonJavaScript

Loading...

Complexity:

• Time: O(n) - each element is visited at most twice (once by right, once by left)
• Space: O(1) - only uses a few integer variables regardless of input size

---

Problem 2: Minimum Window Substring (LC 76)

Description: Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window.

This is a classic “Find Shortest” problem and a favorite among interviewers.

Example:

• Input: s = "ADOBECODEBANC", t = "ABC"
• Output: "BANC"
• Explanation: The minimum window containing A, B, C is “BANC”.

Approach

Use two hash maps:

1. need: Count of each character we need from t
2. window: Count of each character currently in our window

Track valid = number of characters that meet the requirement.

s = "ADOBECODEBANC", t = "ABC"

Expand until valid (contains A, B, C):
[ADOBEC] → valid! len=6, record
Shrink while still valid:
[DOBEC] → missing A, stop

Continue expanding...
[DOBECODEBA] → valid!
[OBECODEBA] → valid! len=9
[BECODEBA] → valid! len=8
[ECODEBA] → missing C, stop

...eventually...
[BANC] → valid! len=4 ✓

Min Window Visualization

Watch how the algorithm finds the minimum window. Notice the key difference: we update the result INSIDE the while loop while the window is valid, then shrink to find an even smaller valid window.

Key Observations:

• Need: Characters required from target string t
• Window: Current character counts in our window
• The result updates while shrinking (inside the while loop)
• We keep shrinking until the window becomes invalid

Naive Map Comparison (O(|Σ| × m + n))

JavaPythonJavaScript

Loading...

Complexity: Time O(|Σ| × m + n); Space O(|Σ|) — included() scans all keys of t each time.

---

Basic Solution: valid Counter (O(m + n))

JavaPythonJavaScript

Loading...

Why O(m + n)?

• Each character is added/removed at most once
• valid == need.size() is O(1) because we update valid only for the touched character
• Total: outer O(m) + init O(n)

---

Optimized Solution: Single Counter Array (O(m + n))

This approach uses a single counter array and a less variable. It has the same O(m + n) complexity as the basic solution, but with cleaner code and slightly better constant factors.

Core Idea: Merge Two Maps into One

Instead of maintaining separate need and window maps, we use:

cnt[c] = (characters needed from t) - (characters we have in window)
       = need[c] - window[c]

What does cnt[c] tell us?

cnt[c] value	Meaning
> 0	Window needs more of character c
= 0	Window has exactly enough of character c
< 0	Window has excess of character c

The less Variable

less = count of character types where cnt[c] > 0 (i.e., insufficient)

When less == 0: Every character type has cnt[c] ≤ 0, meaning the window covers all required characters!

Step-by-Step Example

s = "ADOBEC", t = "ABC"
Initial: cnt = {A:1, B:1, C:1}, less = 3

Step 1: Add 'A'
  cnt[A]-- → cnt = {A:0, B:1, C:1}
  cnt[A] == 0? Yes! less-- → less = 2
  less == 0? No, continue expanding

Step 2: Add 'D'
  cnt[D]-- → cnt = {A:0, B:1, C:1, D:-1}
  cnt[D] == 0? No (it's -1)
  less == 0? No, continue expanding

Step 3: Add 'O'
  cnt[O]-- → cnt = {..., O:-1}
  less == 0? No, continue expanding

Step 4: Add 'B'
  cnt[B]-- → cnt = {A:0, B:0, C:1, ...}
  cnt[B] == 0? Yes! less-- → less = 1
  less == 0? No, continue expanding

Step 5: Add 'E'
  cnt[E]-- → cnt = {..., E:-1}
  less == 0? No, continue expanding

Step 6: Add 'C'
  cnt[C]-- → cnt = {A:0, B:0, C:0, ...}
  cnt[C] == 0? Yes! less-- → less = 0
  less == 0? YES! Window "ADOBEC" is valid!
  
  Now shrink:
    Remove 'A': cnt[A] was 0, so less++ → less = 1
    Window invalid, stop shrinking

Why is the Validity Check O(1)?

// Adding character c to window:
cnt[c]--;
if (cnt[c] == 0) less--;  // O(1) check, O(1) update

// Removing character x from window:
if (cnt[x] == 0) less++;  // O(1) check, O(1) update  
cnt[x]++;

// Validity check:
while (less == 0) { ... }  // O(1) check!

Every operation is O(1), so the total complexity is O(m + n).

JavaPythonJavaScript

Loading...

Complexity (Same as Basic Solution):

• Time: O(m + n) - each character is visited at most twice (once by right, once by left), all operations are O(1)
• Space: O(|Σ|) where |Σ| = 128 for ASCII characters (or 52 for letters only)

Why use this approach?

1. Simpler code: One array instead of two maps
2. Slightly faster: Array access is faster than HashMap
3. Easier to understand: The less variable directly answers “are we done?”

Common Mistakes

1. Forgetting duplicates: If t = "AAB", you need 2 A’s, not just 1
2. Wrong comparison: Use .equals() in Java for Integer objects
3. Off-by-one errors: Window length is right - left + 1

---

Problem 3: Maximum Points from Cards (LC 1423)

Description: Given an array cardPoints and integer k, you can take exactly k cards from the beginning or end of the array. Return the maximum points you can obtain.

Example:

• Input: cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3
• Output: 12
• Explanation: Take three cards from the right: 5 + 6 + 1 = 12.

Approach

This problem looks like it needs DP, but there’s a clever sliding window trick!

Key Insight: If we take k cards from ends, we leave a contiguous subarray of size n-k in the middle.

cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3
n = 7, window_size = n - k = 4

Total sum = 22

Find MINIMUM window sum of size 4:
[1, 2, 3, 4] = 10
[2, 3, 4, 5] = 14
[3, 4, 5, 6] = 18
[4, 5, 6, 1] = 16

Minimum = 10
Answer = 22 - 10 = 12 ✓

This transforms into a Fixed Size Sliding Window problem!

JavaPythonJavaScript

Loading...

Complexity:

• Time: O(n) - we compute the initial window sum and slide through the array once
• Space: O(1) - only uses a few integer variables regardless of input size

---

Problem 4: Count Subarrays Where Max Appears ≥ K Times (LC 2962)

Description: Given an array nums, count subarrays where the global maximum value appears at least k times.

Example:

• Input: nums = [1,3,2,3,3], k = 2
• Global max = 3
• Valid subarrays count = 6

Approach (Sliding Window with Sharing)

1. Precompute maxVal = max(nums).
2. Slide with two pointers. Maintain cntMax = occurrences of maxVal in window.
3. For each right:
   • Add nums[right]; if it equals maxVal, cntMax++.
   • While cntMax >= k, move left rightward (and decrement cntMax when a max leaves).
   • After the while-loop, left is the first index that would make the window invalid again.
   • Contribution: all starts 0..left-1 with end at right are valid ⇒ add left to answer.

Why does ans += left work (sharing idea)?

• When the window first becomes valid, every prefix start before left is valid for the current right.
• As we extend right, these prefixes stay valid until we move left past a maxVal.
• So each right shares the same valid-start region; we just add its size (left) once.

Pseudo-code

maxVal = max(nums)
cntMax = 0; left = 0; ans = 0
for right in 0..n-1:
    if nums[right] == maxVal: cntMax++
    while cntMax >= k:
        if nums[left] == maxVal: cntMax--
        left++
    ans += left   # number of valid starts for this right
return ans

Complexity: Time O(n), Space O(1).

Reference: LC 2962 solution discussion

---

Templates & Patterns

Template 1: Find Longest Valid Subarray

JavaPythonJavaScript

Loading...

Use for: Longest substring without repeating characters, longest subarray with at most K distinct elements, etc.

Template 2: Find Shortest Valid Subarray

JavaPythonJavaScript

Loading...

Use for: Minimum window substring, minimum size subarray sum, etc.

---

When to Use Variable Sliding Window

✅ Use Variable Sliding Window when:

• Finding longest/shortest subarray/substring
• Problem mentions “contiguous” or “consecutive”
• Condition involves at most/at least K of something
• Need to find minimum/maximum subarray satisfying a condition

❌ Don’t use when:

• Elements can be non-contiguous
• Order doesn’t matter (consider sorting instead)
• Need to consider all possible combinations (DP might be better)

Related Patterns

Problem Type	Pattern
Fixed window size	Fixed Sliding Window
Dynamic window size	Variable Sliding Window (this article)
Sum in sorted array	Two Pointers (opposite directions)
Linked list cycle	Fast & Slow Pointers

---

Complexity Analysis

Why is it O(n)?

Total operations = moves of right + moves of left
                 = n + (at most n)
                 = O(2n)
                 = O(n)

The key insight: left only increments, never decrements. So across the entire algorithm, left moves at most n times.

---

Summary

Aspect	Longest Pattern	Shortest Pattern
Goal	Maximize window	Minimize window
Shrink when	Window invalid	Window valid
Update result	After while loop	Inside while loop
Example	LC 487, LC 3	LC 76, LC 209

Key Takeaways:

1. Variable window uses two pointers (left, right)
2. Know the difference between “longest” and “shortest” patterns
3. Update result at the right place
4. Time complexity is O(n), not O(n²)