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.

Screen Shot 2019-11-30 at 4.43.41.png

step1 The maximum value among the three elements of Window is 2 Screen Shot 2019-11-30 at 4.45.17.png

step2 Shift by one, the maximum value among the three elements of Window is 3 Screen Shot 2019-11-30 at 4.48.23.png

step3 Shift by one, the maximum value among the three elements of Window is 6 Screen Shot 2019-11-30 at 4.49.18.png

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 Screen Shot 2019-11-30 at 4.17.08.png Screen Shot 2019-11-30 at 4.17.22.png

Recommended Posts

Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm exercise 6
Algorithm Gymnastics 24 Reverse a Linked List
Python algorithm
Algorithm exercises 13
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 24 Middle of the Linked List
Python memorandum (algorithm)
Dictionary learning algorithm
String search algorithm