bisvarup/sliding window.md

Created July 7, 2022 02:33

Star (0) You must be signed in to star a gist
Fork (0) You must be signed in to fork a gist

Select an option

Learn more about clone URLs
Clone this repository at <script src="https://gist.github.com/bisvarup/46cf3d48a53c38d4cc724ee0c121bd58.js"></script>
Save bisvarup/46cf3d48a53c38d4cc724ee0c121bd58 to your computer and use it in GitHub Desktop.

Download ZIP

Raw

sliding window.md

Sliding window

sliding window maximum

Observations

We need the MAX in the sliding window, and the max item will not fluctuate between max and not max, for example if it's max it will not become not max and again become max. So this hints at not using priority queue.

Approach

Store the indexes of elements in the sliding window in dequeue, dequeue because we need to check if new element is more than the last element of the queue. Also, we need to check if first element of dequeue is less than i-k+1.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment