🪟 Sliding Window Technique — Complete Guide

Index: Sliding Window Index | Parent: Array Index

What is Sliding Window?

A window is a contiguous subarray/substring. Instead of recomputing the window from scratch each time, you slide it — add one element from the right, remove one from the left.

Converts O(n²) → O(n)

Array: [1, 3, 5, 2, 8, 4, 6]
Window size 3:
[1,3,5] → [3,5,2] → [5,2,8] → [2,8,4] → [8,4,6]
 slide right one step each time

When to Use Sliding Window?

Subarray/substring problems
Keywords: "contiguous", "subarray", "substring", "consecutive", "window"
Find max/min/average of subarrays of size k
Find longest/shortest subarray satisfying a condition

Type 1: Fixed Size Window

Window size k is given. Slide and compute.

Template:

function fixedWindow(array $arr, int $k): mixed {
    $n = count($arr);
    if ($n < $k) return null;

    // Compute first window
    $windowSum = array_sum(array_slice($arr, 0, $k));
    $maxSum    = $windowSum;

    // Slide the window
    for ($i = $k; $i < $n; $i++) {
        $windowSum += $arr[$i];        // add new element (right)
        $windowSum -= $arr[$i - $k];   // remove old element (left)
        $maxSum = max($maxSum, $windowSum);
    }

    return $maxSum;
}

Type 2: Variable Size Window

Window grows and shrinks based on a condition.

Template:

function variableWindow(array $arr): int {
    $left = 0;
    $result = 0;
    $windowState = /* some state: sum, count, map */;

    for ($right = 0; $right < count($arr); $right++) {
        // Expand: add arr[right] to window
        // $windowState = update(windowState, arr[$right]);

        // Shrink: while window violates condition, move left
        while (/* window invalid */) {
            // $windowState = remove(windowState, arr[$left]);
            $left++;
        }

        // Window is valid — update result
        $result = max($result, $right - $left + 1);
    }

    return $result;
}

Interview Questions — Sliding Window

Q1. Maximum Sum Subarray of Size K `[E][FB]`

Question: Find max sum of any contiguous subarray of size k.

🧠 How to Approach This

Step 1 — Recognize the pattern:

Fixed-size window. "Contiguous subarray" + "size k" + "max sum" = fixed sliding window.

Step 2 — Brute force (what NOT to do):

For each starting position, sum k elements → O(n×k). With n=10,000, k=1,000 that's 10M operations — and we can do it in O(n).

Step 3 — Optimal insight:

When sliding the window right by one step, you're only making ONE change:

- Add the new right element

- Remove the old left element

No need to resum the entire window!

Step 4 — Algorithm:

1. Compute sum of first window [0..k-1]

2. For i from k to n-1: sum += arr[i] - arr[i-k]

3. Track max sum seen

Step 5 — Edge cases:

- k > n: no valid window, return 0 or throw error

- k = n: entire array is one window

[2,1,5,1,3,2]  k=3
[2,1,5]=8  [1,5,1]=7  [5,1,3]=9 ← max  [1,3,2]=6
                        ↑ answer: 9

function maxSumSubarray(array $arr, int $k): int {
    $n = count($arr);

    // First window
    $windowSum = 0;
    for ($i = 0; $i < $k; $i++) {
        $windowSum += $arr[$i];
    }

    $maxSum = $windowSum;

    // Slide
    for ($i = $k; $i < $n; $i++) {
        $windowSum += $arr[$i] - $arr[$i - $k];
        $maxSum = max($maxSum, $windowSum);
    }

    return $maxSum;
}

echo maxSumSubarray([2,1,5,1,3,2], 3); // 9

function maxSumSubarray(arr, k) {
    let windowSum = arr.slice(0, k).reduce((a, b) => a + b, 0);
    let maxSum = windowSum;
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

Time: O(n) | Space: O(1)

Q2. Smallest Subarray with Sum >= S `[M][FB]`

Question: Find minimum length subarray with sum >= s.

🧠 How to Approach This

Step 1 — Recognize the pattern:

"Minimum length subarray with a condition" = Variable sliding window.

Step 2 — Brute force (what NOT to do):

Check every (start, end) pair: O(n²).

Step 3 — Optimal insight:

Expand window from right until condition is met (sum >= s). Then shrink from left as long as condition STILL holds — because we want the MINIMUM length. Track min length each time condition holds.

Step 4 — Algorithm:

1. left=0, sum=0, minLen=∞

2. Expand right++: sum += arr[right]

3. While sum >= target: minLen = min(minLen, right-left+1); sum -= arr[left]; left++

4. Return minLen (or 0 if no valid window)

Step 5 — Edge cases:

- No subarray meets condition: return 0

- Single element >= s: return 1

- All elements less than s: elements must combine to reach s

[2,3,1,2,4,3]  s=7
Expand right until sum>=7:
[2,3,1,2] sum=8>=7 → min=4, shrink left
[3,1,2] sum=6<7 → expand
[3,1,2,4] sum=10>=7 → min=4, shrink
[1,2,4] sum=7>=7 → min=3, shrink
[2,4] sum=6<7 → expand
[2,4,3] sum=9>=7 → min=3, shrink
[4,3] sum=7>=7 → min=2 ← answer!

function minSubarrayLen(int $target, array $arr): int {
    $left    = 0;
    $sum     = 0;
    $minLen  = PHP_INT_MAX;

    for ($right = 0; $right < count($arr); $right++) {
        $sum += $arr[$right]; // expand

        while ($sum >= $target) {
            $minLen = min($minLen, $right - $left + 1);
            $sum -= $arr[$left]; // shrink
            $left++;
        }
    }

    return $minLen === PHP_INT_MAX ? 0 : $minLen;
}

echo minSubarrayLen(7, [2,3,1,2,4,3]); // 2

Q3. Longest Substring Without Repeating Characters `[M][FB]`

Question: Find length of longest substring with all unique chars.

🧠 How to Approach This

Step 1 — Recognize the pattern:

"Longest substring with condition (all unique)" = Variable sliding window + hash map.

Step 2 — Brute force (what NOT to do):

Check every substring for uniqueness: O(n³) or O(n²) with a set. Can do O(n).

Step 3 — Optimal insight:

Track the last seen index of each character. When you encounter a duplicate at position right:

- Jump left pointer to max(left, lastSeen[char]+1)

- The max() is crucial — don't jump left backwards!

Step 4 — Algorithm:

1. seen = {} (char → last index), left=0, maxLen=0

2. For right in 0..n-1:

- If seen[s[right]] exists AND >= left: update left = seen[s[right]] + 1

- seen[s[right]] = right

- maxLen = max(maxLen, right - left + 1)

Step 5 — Edge cases:

- All unique: left never moves, window spans entire string

- All same chars ("aaaa"): window always size 1

- Two-char repeats: window size 2

"abcabcbb"
a→ window=[a] len=1
b→ window=[a,b] len=2
c→ window=[a,b,c] len=3
a→ 'a' seen at 0! left=max(left, 0+1)=1, window=[b,c,a] len=3
b→ 'b' seen at 1! left=max(left, 1+1)=2, window=[c,a,b] len=3
c→ 'c' seen at 2! left=max(left, 2+1)=3, window=[a,b,c] len=3
b→ 'b' seen at 4! left=max(left, 4+1)=5, window=[c,b] len=2
b→ 'b' seen at 6! left=max(left, 6+1)=7, window=[b] len=1
Answer: 3

function lengthOfLongestSubstring(string $s): int {
    $seen  = []; // char => last seen index
    $left  = 0;
    $maxLen = 0;

    for ($right = 0; $right < strlen($s); $right++) {
        $char = $s[$right];

        // If seen and within current window
        if (isset($seen[$char]) && $seen[$char] >= $left) {
            $left = $seen[$char] + 1; // jump past last occurrence
        }

        $seen[$char] = $right;
        $maxLen = max($maxLen, $right - $left + 1);
    }

    return $maxLen;
}

echo lengthOfLongestSubstring("abcabcbb"); // 3
echo lengthOfLongestSubstring("bbbbb");    // 1
echo lengthOfLongestSubstring("pwwkew");   // 3 ("wke")

function lengthOfLongestSubstring(s) {
    const seen = new Map();
    let left = 0, maxLen = 0;
    for (let right = 0; right < s.length; right++) {
        if (seen.has(s[right]) && seen.get(s[right]) >= left) {
            left = seen.get(s[right]) + 1;
        }
        seen.set(s[right], right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

Time: O(n) | Space: O(min(n, charset))

Q4. Longest Subarray with K Distinct Characters `[M]`

Question: Find longest substring with at most k distinct characters.

🧠 How to Approach This

Step 1 — Recognize the pattern:

"Longest subarray/substring with AT MOST k distinct values" = Variable sliding window + frequency map.

Step 2 — Key insight:

Track frequency of each character in the current window. When distinct count > k, shrink from left until it's back to k.

Step 3 — Algorithm:

1. freq = {}, left=0, maxLen=0

2. Expand right: freq[s[right]]++

3. While count(freq) > k: freq[s[left]]--; if freq=0 remove; left++

4. maxLen = max(maxLen, right - left + 1)

Step 4 — Edge cases:

- k >= distinct chars in string: entire string is the answer

- k = 0: return 0 (no characters allowed)

- k = 1: find longest run of any single character

function longestSubarrayKDistinct(string $s, int $k): int { $freq = []; $left = 0; $maxLen = 0;

for ($right = 0; $right < strlen($s); $right++) { $char = $s[$right]; $freq[$char] = ($freq[$char] ?? 0) + 1;

// Shrink while more than k distinct chars while (count($freq) > $k) { $leftChar = $s[$left]; $freq[$leftChar]--; if ($freq[$leftChar] === 0) unset($freq[$leftChar]); $left++; }

$maxLen = max($maxLen, $right - $left + 1); }

return $maxLen; }

echo longestSubarrayKDistinct("araaci", 2); // 4 ("araa") echo longestSubarrayKDistinct("araaci", 1); // 2 ("aa")


---

### Q5. Maximum Average Subarray of Size K `[E]`

**Question:** Find contiguous subarray of size k with maximum average.

---

> **🧠 How to Approach This**
>
> **Step 1 — Recognize the pattern:**
> Fixed window of size k, maximize average = maximize sum (same thing).
>
> **Step 2 — Key insight:**
> Maximizing average = maximizing sum (since k is constant). Use fixed window sliding.
>
> **Step 3 — Algorithm:**
> Same as Q1 (max sum subarray of size k), then divide by k at the end.

function findMaxAverage(array $nums, int $k): float { $sum = array_sum(array_slice($nums, 0, $k)); $max = $sum;

for ($i = $k; $i < count($nums); $i++) { $sum += $nums[$i] - $nums[$i - $k]; $max = max($max, $sum); }

return $max / $k; }

echo findMaxAverage([1,12,-5,-6,50,3], 4); // 12.75


---

### Q6. Permutation in String `[M][FB]`

**Question:** Does `s2="eidbaooo"` contain a permutation of `s1="ab"`?

---

> **🧠 How to Approach This**
>
> **Step 1 — Recognize the pattern:**
> "Does s2 contain a permutation of s1?" = Fixed window of size len(s1), check character frequency match.
>
> **Step 2 — Key insight:**
> A permutation has the same character frequencies as the original. So: slide a window of size len(s1) over s2. At each position, compare frequency maps. If they match → found a permutation.
>
> **Step 3 — Algorithm:**
> 1. Build frequency map of s1
> 2. Build frequency map of first window in s2
> 3. If maps match → return true
> 4. Slide: add s2[right], remove s2[right-k]; compare after each slide
>
> **Step 4 — Edge cases:**
> - len(s1) > len(s2): impossible, return false
> - s1 = s2: one window, match found immediately

function checkInclusion(string $s1, string $s2): bool { $k = strlen($s1); $n = strlen($s2); if ($k > $n) return false;

$need = array_fill_keys(str_split($s1), 0); $have = [];

foreach (str_split($s1) as $c) $need[$c]++;

// Build first window for ($i = 0; $i < $k; $i++) { $c = $s2[$i]; $have[$c] = ($have[$c] ?? 0) + 1; }

if ($need == $have) return true;

// Slide for ($i = $k; $i < $n; $i++) { // Add right char $c = $s2[$i]; $have[$c] = ($have[$c] ?? 0) + 1;

// Remove left char $leftChar = $s2[$i - $k]; $have[$leftChar]--; if ($have[$leftChar] === 0) unset($have[$leftChar]);

// Compare (only relevant keys) if ($need == $have) return true; }

return false; }

var_dump(checkInclusion("ab", "eidbaooo")); // true ("ba" at index 3)


---

### Q7. Max Consecutive Ones After Flipping K Zeros `[M][FB]`

**Question:** `[1,1,0,0,1,1,1,0,1]`, flip at most k=2 zeros. Max consecutive 1s?

---

> **🧠 How to Approach This**
>
> **Step 1 — Recognize the pattern:**
> "Longest window with at most k violations (zeros)" = Variable sliding window counting zeros.
>
> **Step 2 — Key insight:**
> Instead of actually flipping zeros, count them. Keep a window where zeroCount <= k. When it exceeds k, shrink from left until it's back to k.
>
> **Step 3 — Algorithm:**
> 1. left=0, zeros=0, maxLen=0
> 2. Expand right: if nums[right]=0, zeros++
> 3. While zeros > k: if nums[left]=0, zeros--; left++
> 4. maxLen = max(maxLen, right - left + 1)
>
> **Step 4 — Edge cases:**
> - k=0: find longest run of 1s (no flips allowed)
> - k >= total zeros: entire array is one window
> - All zeros: max window size = k

function longestOnes(array $nums, int $k): int { $left = 0; $zeros = 0; $maxLen = 0;

for ($right = 0; $right < count($nums); $right++) { if ($nums[$right] === 0) $zeros++;

while ($zeros > $k) { if ($nums[$left] === 0) $zeros--; $left++; }