Category: Sliding Window
Sliding Window Concepts
Posted on
The Sliding Window technique is usually used to find the shortest or longest qualified subarray. For example, find the shortest subarray whose sum is no less than K. A Naive Idea The problem is straightforward if, for every right index, we could find the rightmost left index so that the window has sum >= K….
Sliding Window & Monotonic Queue
Posted on
Summary A typical sliding window problem requires the longest or shortest subarray which satisfies certain constraints. The constraint must satisfy a monotonic property: as the right end of the window increases, the left end won’t decrease. If the constrain is related to maximum or minimum, we could use Monotonic Queues, which are perfect data structures…