Question 1

Count subarrays with sum exactly k. nums may contain negative numbers. Which approach is correct in O(n)?

Accepted Answer

Prefix sums with a hash map of prefix counts With negatives, extending a window can lower the sum, so the shrink rule is not monotonic and a window misses answers. Counting earlier prefixes equal to prefix minus k handles any values. A fixed size k window confuses the target with a length. Sorting destroys contiguity.

Question 2

Longest substring without repeating characters. Which shrink step is right?for r, ch in enumerate(s):
 count[ch] += 1
 # shrink here
 best = max(best, r - l + 1)

Accepted Answer

while count[ch] > 1: count[s[l]] -= 1; l += 1 The window is valid only after the duplicate of ch leaves, which can take several steps, so it must be while. A single if step leaves a duplicate in the window for inputs like "abcb". Setting l = r discards valid characters and leaves stale counts, so later windows are judged wrong. Moving l without decrementing counts never clears the duplicate and loops forever.

Question 3

Minimum Window Substring (shortest substring of s that contains every character of t, with counts) over s of length m and t of length n with a need counter. What is the time complexity?

Accepted Answer

O(m + n) Each index of s enters and leaves the window at most once, and building the need counter costs O(n). O(m n) assumes rechecking all of t per step, which a formed counter avoids. O(m^2) is trying every start. Nothing is sorted, so no log factor.

Question 4

Longest Repeating Character Replacement: longest substring of one repeated letter after at most k letter changes. When is the window [l, r] invalid?

Accepted Answer

(r - l + 1) - max_count > k The cells not equal to the majority letter must be replaced, which is window length minus max_count, and that must be at most k. max_count above k is fine because those letters need no change. Length above k ignores the majority. Distinct letters do not count replacements; "aab" has 2 distinct but needs 1 change.

Question 5

Max average of a contiguous subarray of length exactly k, n up to 10^5. Which approach is optimal?

Accepted Answer

A running window sum, O(n) Add the entering value and subtract the leaving one: O(n). Recomputing is O(n k). Sorting breaks contiguity. A monotonic deque is O(n) too but solves window max, not sum, so it is the wrong tool here.

Question 6

Does s2 contain a permutation of s1, lowercase letters? Which window works?

Accepted Answer

Fixed window of len(s1) with 26 counts, compare on each slide A permutation has exactly len(s1) characters, so a fixed window with count compare is O(26 n). A growing variable window can contain extra letters and still pass. Sorting every window is O(n k log k). The set check ignores counts and contiguity.

Question 7

Minimum Size Subarray Sum: positive integers, find the shortest subarray with sum >= target. Why is a sliding window valid here?

Accepted Answer

All values are positive, so shrinking always decreases the sum Positivity makes the window sum monotonic in both pointers, so greedy shrinking is safe. The array is not sorted. A positive target alone does not help if values can be negative. Prefix sums with binary search also work in O(n log n), but the window is valid and O(n).

Question 8

Max Consecutive Ones III: binary array, flip at most k zeros to get the longest run of 1s. Approach?

Accepted Answer

Variable window counting zeros. Extend r, and while zeros > k move l and decrement zeros when leaving a zero. Track max length. O(n) time, O(1) space. Pitfall: using if instead of while.

Sliding window coding interview questions

More coding topics

Practise these on your commute