Algorithm gymnastics 2

Find Maximum in Sliding Window

Description

Given an array of integers and a Window of size w, finds the current maximum value in the Window as the Window (part of the array) slides through the array.

Example

With a Window Size of 3, let's find all the maximums as we slide.

step1 The maximum value among the three elements of Window is 2

step2 Shift by one, the maximum value among the three elements of Window is 3

step3 Shift by one, the maximum value among the three elements of Window is 6

Finally, the data structure containing 2 3 6 should be returned.

Solution

Time Complexity: O(n) All elements are pushed and popped from the deque only once in a single scan. Push and pop are O (1), so The algorithm works with Time Complexity O (n).

Space Complexity: O(w) Space Complexity is O (w) because it uses a list of Window sizes.

Rough algorithm flow

This algorithm uses a deque data structure to find the maximum value in the window. The purpose of using this data structure is to push and pop operations such as adding and deleting data to both ends. This is because the deque that works with O (1). This acts as a window. There are two points to note here.

1. Put the index of the element, not the element of the array, in the deque.
2. Put the maximum index at the beginning of the deque and the other indexes at the end.

At the beginning of the algorithm, the deque is a deque, so add the index of the element by the size of the first window.

If the element you add is smaller than the element after the deque, the element you add will be the last element of the new deque. If the element to add is larger, pop the element repeatedly from behind the deque until you find a larger element. Push the new element you want to add as the end.

As you can see, the deque stores the elements in descending order. The deque begins with the index of the maximum value for that particular window.

Repeat the following steps each time the window moves to the right.

1. If the element behind the deque is less than or equal to the current element to be added, remove the element from the deque until the index of the element larger than the element to be added appears.
2. If you shift one window and the value does not fit in the current window, the first element index is deleted.
3. Push the index of the current element to the back of the window.

Code