Find maximum for every window of size k in an array – Google Interview Question

Problem

This is a hard problem that was asked by Google in a software engineering interview.

Given an array of integers and a number k, where 1 <= k <= length of the array, compute the maximum values of each subarray of length k and print the max values.

Contents

Solution

The key to solving this problem in O(n) runtime and O(k) space is to use the Dequeue data structure (Double Ended Queue). The index of elements are stored in the dequeue.

A dequeue of size k is created. The maximum element for a window is stored at the front of the queue and any useless elements are discarded and elements that are outside of the window are discarded.

Useless element – If the current element is greater than the last element in the dequeue, the last element in the dequeue can be discarded as it is useless.

The way that code above works is in the first for loop we loop through the first k element in the array.

A while loop is used to check whether the current element that we are looking at in the array is greater than the last element in the dequeue and if it is then we remove that last element in the dequeue.

Once that is completed we add the current element index to the end of the dequeue (line 18).

Then in the second for loop we loop through the rest of the elements in the array.

Firstly we print out the array index for the front of the dequeue as that is the largest value in the current window.

Then the dequeue is scanned in the while loop from front to end to check whether there are any indexes in the dequeue that are outside the current window. If there are these indexes are removed.

The second while loop is then executed and it is the same as the while loop in line 15. It checks the current element against the last element in the dequeue to see if it is a useless element.

Once the second for loop has ended, there is final print out to print the max value in the last window.

Runtime complexity

The runtime complexity for this algorithm is O(n).

The runtime is O(n) because the array is only traversed once, each element is only look at once. Also an element is at most enqueued and dequeued at most once. The while loops traverse the dequeue but this is at most equal to the number of times we get to the while loop. So therefore it is O(n+n+n) = O(n).

Space Complexity

The space complexity for this algorithm is O(k). JakTech

1 Response

This site uses Akismet to reduce spam. Learn how your comment data is processed.