Autocoder

Sliding window interview questions with worked solutions

Last updated 2026-11-19

A sliding window keeps a contiguous range of an array or string and updates its summary as the right edge moves forward and the left edge catches up. Because each index enters and leaves the window at most once, a problem that looks O(n^2) becomes O(n).

There are two forms. A fixed window has a given size k and slides one step at a time. A variable window grows until a condition breaks and then shrinks from the left until it holds again. The problems below cover both, then finish with the harder minimum window and monotonic deque cases. See also two pointers questions and the DSA coding round guide.

Problems10, fixed and variable windows
LanguagesPython and Java
Core ideaEach index enters and leaves once

Template for a variable window

Expand with a right pointer, add the new element to your summary, then while the window is invalid, remove the left element and advance the left pointer. Record the answer either after the shrink loop (for the longest valid window) or inside it (for the shortest).

The window summary is the key design choice: a sum, a count array, a map of frequencies, or a deque for the maximum.

Limits of the pattern

Negative numbers break sum-based windows because adding an element no longer moves the sum in one direction. In that case use prefix sums with a hash map instead.

Sliding window interview questions with worked solutions: questions with worked answers

  1. 1

    Maximum sum of any subarray of size k.

    easy

    Compute the sum of the first k elements, then slide: add the new element and subtract the one leaving. Track the maximum. This avoids recomputing each window from scratch. Time O(n), space O(1).. Edge cases: k larger than the array is invalid, k equal to n, negative values (still fine for fixed windows).

    python
    def max_sum_k(a, k):
        if k > len(a):
            raise ValueError("k too large")
        s = sum(a[:k])
        best = s
        for i in range(k, len(a)):
            s += a[i] - a[i - k]
            best = max(best, s)
        return best
    java
    import java.util.*;
    
    class Solution {
        static long maxSumK(int[] a, int k) {
            if (k > a.length) throw new IllegalArgumentException("k too large");
            long s = 0;
            for (int i = 0; i < k; i++) s += a[i];
            long best = s;
            for (int i = k; i < a.length; i++) {
                s += a[i] - a[i - k];
                best = Math.max(best, s);
            }
            return best;
        }
    }
  2. 2

    Longest substring without repeating characters.

    easy

    Store the last index of each character. When the new character was seen inside the current window, move the left edge just past its previous position. Never move left backwards. Update the best length every step. Time O(n), space O(k) for the alphabet.. Edge cases: empty string, all same characters, a repeat that lies before the window start.

    python
    def length_of_longest_substring(s):
        last, l, best = {}, 0, 0
        for r, ch in enumerate(s):
            if ch in last and last[ch] >= l:
                l = last[ch] + 1
            last[ch] = r
            best = max(best, r - l + 1)
        return best
    java
    import java.util.*;
    
    class Solution {
        static int lengthOfLongestSubstring(String s) {
            Map<Character, Integer> last = new HashMap<>();
            int l = 0, best = 0;
            for (int r = 0; r < s.length(); r++) {
                char ch = s.charAt(r);
                if (last.containsKey(ch) && last.get(ch) >= l) l = last.get(ch) + 1;
                last.put(ch, r);
                best = Math.max(best, r - l + 1);
            }
            return best;
        }
    }
  3. 3

    Smallest subarray with sum at least a target (positive numbers).

    medium

    Grow the window by adding a[r]. While the sum is at least the target, record the length and then remove a[l], advancing l. This is the shortest-window form: the answer is updated inside the shrink loop. Positive values guarantee that shrinking only lowers the sum. Time O(n), space O(1).. Edge cases: no valid window (return 0), one element already enough, target 0.

    python
    def min_subarray_len(target, a):
        l = s = 0
        best = float('inf')
        for r, x in enumerate(a):
            s += x
            while s >= target:
                best = min(best, r - l + 1)
                s -= a[l]
                l += 1
        return 0 if best == float('inf') else best
    java
    import java.util.*;
    
    class Solution {
        static int minSubArrayLen(int target, int[] a) {
            int l = 0, best = Integer.MAX_VALUE;
            long s = 0;
            for (int r = 0; r < a.length; r++) {
                s += a[r];
                while (s >= target) {
                    best = Math.min(best, r - l + 1);
                    s -= a[l++];
                }
            }
            return best == Integer.MAX_VALUE ? 0 : best;
        }
    }
  4. 4

    Count subarrays whose product is less than k (all positive numbers).

    medium

    Keep the product of the window. While it reaches k, divide out a[l] and advance l. Every subarray ending at r and starting between l and r qualifies, so add r - l + 1. If k is 1 or less, no positive product can qualify. Time O(n), space O(1).. Edge cases: k <= 1 (answer 0), a single element at least k, many ones.

    python
    def num_subarray_product_less_than_k(a, k):
        if k <= 1:
            return 0
        prod, l, count = 1, 0, 0
        for r, x in enumerate(a):
            prod *= x
            while prod >= k:
                prod //= a[l]
                l += 1
            count += r - l + 1
        return count
    java
    import java.util.*;
    
    class Solution {
        static int numSubarrayProductLessThanK(int[] a, int k) {
            if (k <= 1) return 0;
            long prod = 1;
            int l = 0, count = 0;
            for (int r = 0; r < a.length; r++) {
                prod *= a[r];
                while (prod >= k) prod /= a[l++];
                count += r - l + 1;
            }
            return count;
        }
    }
  5. 5

    Max consecutive ones III: longest run of 1s if you may flip at most k zeroes.

    medium

    Maintain the number of zeroes in the window. If it exceeds k, shrink from the left, reducing the zero count when a zero leaves. The window is always valid after the loop, so its length is a candidate. Time O(n), space O(1).. Edge cases: k = 0 (plain longest run), all ones, all zeroes with small k.

    python
    def longest_ones(a, k):
        l = zeros = best = 0
        for r, x in enumerate(a):
            if x == 0:
                zeros += 1
            while zeros > k:
                if a[l] == 0:
                    zeros -= 1
                l += 1
            best = max(best, r - l + 1)
        return best
    java
    import java.util.*;
    
    class Solution {
        static int longestOnes(int[] a, int k) {
            int l = 0, zeros = 0, best = 0;
            for (int r = 0; r < a.length; r++) {
                if (a[r] == 0) zeros++;
                while (zeros > k) if (a[l++] == 0) zeros--;
                best = Math.max(best, r - l + 1);
            }
            return best;
        }
    }
  6. 6

    Longest repeating character replacement: longest substring after replacing at most k characters.

    medium

    A window is valid when its length minus the count of its most frequent letter is at most k. Track counts and the highest frequency seen. It is safe not to decrease that maximum when shrinking, since only a larger maximum can produce a longer answer. Shrink by one step at a time. Time O(n), space O(26).. Edge cases: k = 0, k at least the length, a single repeated letter.

    python
    def character_replacement(s, k):
        cnt = [0] * 26
        l = maxf = best = 0
        for r, ch in enumerate(s):
            cnt[ord(ch) - 65] += 1
            maxf = max(maxf, cnt[ord(ch) - 65])
            if r - l + 1 - maxf > k:
                cnt[ord(s[l]) - 65] -= 1
                l += 1
            best = max(best, r - l + 1)
        return best
    java
    import java.util.*;
    
    class Solution {
        static int characterReplacement(String s, int k) {
            int[] cnt = new int[26];
            int l = 0, maxf = 0, best = 0;
            for (int r = 0; r < s.length(); r++) {
                maxf = Math.max(maxf, ++cnt[s.charAt(r) - 'A']);
                if (r - l + 1 - maxf > k) cnt[s.charAt(l++) - 'A']--;
                best = Math.max(best, r - l + 1);
            }
            return best;
        }
    }
  7. 7

    Permutation in string: does s2 contain a permutation of s1 as a substring?

    medium

    Use a fixed window of length len(s1) over s2. Keep a count array for s1 and one for the current window, and compare them after each slide. Comparing two arrays of 26 is constant work, so the total stays linear in len(s2). Time O(26 * n), space O(26).. Edge cases: s1 longer than s2 (false), identical strings, repeated letters.

    python
    def check_inclusion(s1, s2):
        n, m = len(s1), len(s2)
        if n > m:
            return False
        a, b = [0] * 26, [0] * 26
        for i in range(n):
            a[ord(s1[i]) - 97] += 1
            b[ord(s2[i]) - 97] += 1
        for i in range(n, m):
            if a == b:
                return True
            b[ord(s2[i]) - 97] += 1
            b[ord(s2[i - n]) - 97] -= 1
        return a == b
    java
    import java.util.*;
    
    class Solution {
        static boolean checkInclusion(String s1, String s2) {
            int n = s1.length(), m = s2.length();
            if (n > m) return false;
            int[] a = new int[26], b = new int[26];
            for (int i = 0; i < n; i++) {
                a[s1.charAt(i) - 'a']++;
                b[s2.charAt(i) - 'a']++;
            }
            for (int i = n; i < m; i++) {
                if (Arrays.equals(a, b)) return true;
                b[s2.charAt(i) - 'a']++;
                b[s2.charAt(i - n) - 'a']--;
            }
            return Arrays.equals(a, b);
        }
    }
  8. 8

    Minimum window substring: smallest window of s containing all characters of t.

    hard

    Track how many required characters are still missing. Expand right: decrement need[ch], and if it was positive, lower the missing count. When nothing is missing, record the window and shrink from the left, restoring need and raising missing when a required character leaves. Characters not in t simply go negative in need. Time O(n + m), space O(alphabet).. Edge cases: t longer than s, no valid window (empty string), duplicate characters in t.

    python
    from collections import Counter
    
    def min_window(s, t):
        if not t or len(t) > len(s):
            return ""
        need = Counter(t)
        missing, l = len(t), 0
        best = (0, float('inf'))
        for r, ch in enumerate(s):
            if need[ch] > 0:
                missing -= 1
            need[ch] -= 1
            while missing == 0:
                if r - l + 1 < best[1] - best[0]:
                    best = (l, r + 1)
                need[s[l]] += 1
                if need[s[l]] > 0:
                    missing += 1
                l += 1
        return "" if best[1] == float('inf') else s[best[0]:best[1]]
    java
    import java.util.*;
    
    class Solution {
        static String minWindow(String s, String t) {
            if (t.isEmpty() || t.length() > s.length()) return "";
            int[] need = new int[128];
            for (char c : t.toCharArray()) need[c]++;
            int missing = t.length(), l = 0, start = 0, len = Integer.MAX_VALUE;
            for (int r = 0; r < s.length(); r++) {
                if (need[s.charAt(r)]-- > 0) missing--;
                while (missing == 0) {
                    if (r - l + 1 < len) { len = r - l + 1; start = l; }
                    if (++need[s.charAt(l++)] > 0) missing++;
                }
            }
            return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
        }
    }
  9. 9

    Sliding window maximum: the maximum of every window of size k.

    hard

    Keep a deque of indices whose values are in decreasing order. Before pushing index i, pop smaller values from the back, since they can never be a maximum while a larger, newer value is in the window. Pop the front if it has left the window. The front is the maximum. Each index is pushed and popped once. Time O(n), space O(k).. Edge cases: k = 1, k = n, equal values (pop with <= or <, both work), decreasing input.

    python
    from collections import deque
    
    def max_sliding_window(a, k):
        dq, out = deque(), []
        for i, x in enumerate(a):
            while dq and a[dq[-1]] <= x:
                dq.pop()
            dq.append(i)
            if dq[0] <= i - k:
                dq.popleft()
            if i >= k - 1:
                out.append(a[dq[0]])
        return out
    java
    import java.util.*;
    
    class Solution {
        static int[] maxSlidingWindow(int[] a, int k) {
            Deque<Integer> dq = new ArrayDeque<>();
            int[] out = new int[a.length - k + 1];
            for (int i = 0; i < a.length; i++) {
                while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();
                dq.addLast(i);
                if (dq.peekFirst() <= i - k) dq.pollFirst();
                if (i >= k - 1) out[i - k + 1] = a[dq.peekFirst()];
            }
            return out;
        }
    }
  10. 10

    Subarrays with exactly K distinct integers: count them.

    hard

    Counting "exactly K" directly is awkward, but "at most K" is a clean variable window. The answer is atMost(K) minus atMost(K - 1). In atMost, grow right, shrink left while distinct values exceed the limit, and add r - l + 1 for each right end. Time O(n), space O(n).. Edge cases: K larger than the number of distinct values (0), K = 1, all values equal.

    python
    def subarrays_with_k_distinct(a, k):
        def at_most(k):
            if k <= 0:
                return 0
            cnt, l, res = {}, 0, 0
            for r, x in enumerate(a):
                cnt[x] = cnt.get(x, 0) + 1
                while len(cnt) > k:
                    cnt[a[l]] -= 1
                    if cnt[a[l]] == 0:
                        del cnt[a[l]]
                    l += 1
                res += r - l + 1
            return res
        return at_most(k) - at_most(k - 1)
    java
    import java.util.*;
    
    class Solution {
        static int subarraysWithKDistinct(int[] a, int k) {
            return atMost(a, k) - atMost(a, k - 1);
        }
        static int atMost(int[] a, int k) {
            if (k <= 0) return 0;
            Map<Integer, Integer> cnt = new HashMap<>();
            int l = 0, res = 0;
            for (int r = 0; r < a.length; r++) {
                cnt.merge(a[r], 1, Integer::sum);
                while (cnt.size() > k) {
                    if (cnt.merge(a[l], -1, Integer::sum) == 0) cnt.remove(a[l]);
                    l++;
                }
                res += r - l + 1;
            }
            return res;
        }
    }

Frequently asked questions

How do I decide between a fixed and a variable window?

If the statement gives a size k, use a fixed window. If it asks for the longest or shortest range satisfying a condition, use a variable window.

Why is sliding window O(n) when there is a loop inside a loop?

The left pointer only moves forward and never exceeds the right, so across the whole run it moves at most n times. Total work is at most 2n steps.

Does sliding window work with negative numbers?

Not for sum conditions, because shrinking no longer reduces the sum. Use prefix sums with a hash map, or a monotonic deque for window extremes.

What is the usual mistake with variable windows?

Updating the answer at the wrong moment: after shrinking for the longest window, inside the shrink loop for the shortest. Test on a tiny input to see which is right.

Where does the monotonic deque come from?

It is the same idea as a monotonic stack, applied at both ends so old elements can expire.

Related guides

More in DSA Interview Questions

See all in this section