Sliding Window

Question 1

What two types of windows are there

Answer 1

variable and fixed

Question 2

How do we keep sliding window o(n)?

Answer 2

the left and the right pointers should only traverse the array once.

Question 3

what operations happen in a variable size sliding windo

Answer 3

each element is at most processed twice, once when expanding and once when contracting

Question 3

what operations happen in fixed-size sliding window

Answer 3

each element is added to the windo once and removed once

Question 4

list out the various techniques for sliding window and their runtimes

Answer 4

Fixed size sliding window o(n)
Variable size sliding window o(n)
Sliding Window with Deque o(n)
Sliding Window with Sorting Heap o(n)