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.
| Problems | 10, fixed and variable windows |
|---|---|
| Languages | Python and Java |
| Core idea | Each 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.
- Longest window with a property: update the answer after making the window valid.
- Shortest window meeting a condition: update the answer inside the shrink loop.
- Counting subarrays: add right - left + 1 per right end.
- Exactly K: compute at most K minus at most K-1.
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 Maximum sum of any subarray of size k.
easyCompute 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).
pythondef 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 bestjavaimport 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 Longest substring without repeating characters.
easyStore 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.
pythondef 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 bestjavaimport 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 Smallest subarray with sum at least a target (positive numbers).
mediumGrow 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.
pythondef 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 bestjavaimport 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 Count subarrays whose product is less than k (all positive numbers).
mediumKeep 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.
pythondef 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 countjavaimport 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 Max consecutive ones III: longest run of 1s if you may flip at most k zeroes.
mediumMaintain 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.
pythondef 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 bestjavaimport 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 Longest repeating character replacement: longest substring after replacing at most k characters.
mediumA 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.
pythondef 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 bestjavaimport 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 Permutation in string: does s2 contain a permutation of s1 as a substring?
mediumUse 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.
pythondef 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 == bjavaimport 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 Minimum window substring: smallest window of s containing all characters of t.
hardTrack 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.
pythonfrom 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]]javaimport 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 Sliding window maximum: the maximum of every window of size k.
hardKeep 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.
pythonfrom 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 outjavaimport 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 Subarrays with exactly K distinct integers: count them.
hardCounting "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.
pythondef 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)javaimport 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
- Two pointers interview questions with worked solutions
- String interview questions with worked solutions
- Prefix sum interview questions with worked solutions
- Monotonic stack interview questions with worked solutions
- Queue and deque interview questions with worked solutions
- Hashing interview questions with worked solutions
More in DSA Interview Questions
- Sorting algorithm interview questions with worked solutions
- Stack interview questions with worked solutions
- String interview questions with worked solutions
- Top K elements interview questions with worked solutions
- Topological Sort Interview Questions
- Tree DP Interview Questions
- Tree Traversal Interview Questions
- Trie (Prefix Tree) Interview Questions
- Two pointers interview questions with worked solutions
- Union-Find (Disjoint Set Union) Interview Questions
- Array interview questions with worked solutions
- Backtracking interview questions with worked solutions