Sliding Window

Question 1

What do you use sliding window for? How does it work

Answer 1

How it works:
- It involves maintaining a dynamic window that slides through the array or string, adjusting its boundaries as needed to track relevant elements or characters. The window is used to slide over the data in chunks corresponding to the window size, and this can be set according to the problem’s requirements. It may be viewed as a variation of the two pointers pattern, with the pointers being used to set the window bounds.

What to use it for:
- contiguous data
- processing subsets of elements

We are working with a list or array or string (ordered collection), and we want a sub-collection, where order matters. And this should not be confused with sub-sequence.
Runtime complexity is usually linear
Conditions:
When we want to satisfy some requirements and find the min or max of a metric.
The size of the window is k
Usually that metric should be changing monotonically: monotonicity make the condition of contraction very easy: e.g. we contract until the condition is not met anymore.
We sometimes minimize and sometimes maximize something.
When we contract (AKA catch up), we sometimes increment the left pointer one by one. Sometimes we just jump left to righ

Question 2

Why is sliding window efficient compared to brute force O(kn)?

Answer 2

Instead of visiting all elements and their asssociated subarrays O(kn) where n is the length of the arry and k is the length of the subarray, we can simply add and substract elements from the subarray window and update a tracking variable according to the problem which makes the run time O(n). This also allows tracking for the current window to be a constant time operation because the variable updates are O(1) constant.

Question 3

What are the subtypes of sliding window problems?

Answer 3

Fixed sliding window sized problems

Variable sized sliding window problems

Count based sliding window problems

Maximum and minimum sliding window

Binary and Boolean

2 sum and subarray sums

Sliding window Median problems

Question 4

What are the most common example problems for the sliding window pattern?

Answer 4

Maximum Sum of a Subarray of Size K

First Negative Number in Every Window of Size K

Longest substring without repeating characters

Question 5

How do I solve a sliding window problem?

Answer 5

When we contract (AKA catch up), we sometimes increment the left pointer one by one. Sometimes we just jump left to right

The size of the window is always r- l + 1 (right index and left index)

Recognize two things:
When the window is valid
How do we change the left pointer (one by one or jumping to right)

Setting it up:

track window state
left = 0
for right in range(len(input))
- move right update window state

while monotonic check(window_state)
- ans = combine(ans, window_state)
- move left update window state
- left += 1

ans = combine(ans, window_state)

eventually return ans

Question 6

What is the runtime and space complexity of the sliding window pattern?

Answer 6

Runtime: O(n)
Note that this assumes the the updating state and also check for validity of the window is done in O(1). Usually we amortize the update of the state so it becomes O(1)

Space complexity: O(window size) = O(n)

Question 7

Name the most popular sliding window problems on leetcode?

Answer 7

longest substring without repeating characters

maximum subarray sum

minimum-number-of-k-consecutive-bit-flips

minimum swaps to group all 1s together

count subarrays with fixed bounds

longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit

frequency-of-the-most-frequent-element