Minimum value of maximum values in sub-segments ... in O(n) complexity

Question

I interviewed with Amazon a few days ago. I could not answer one of the questions the asked me to their satisfaction. I have tried to get the answer after the interview but I have not been successful so far. Here is the question:

You have an array of integers of size n. You are given parameter k where k < n. For each segment of consecutive elements of size k in the array you need to calculate the maximum value. You only need to return the minimum value of these maximum values.

For instance given 1 2 3 1 1 2 1 1 1 and k = 3 the answer is 1.
The segments would be 1 2 3, 2 3 1, 3 1 1, 1 1 2, 1 2 1, 2 1 1, 1 1 1.
The maximum values in each segment are 3, 3, 3, 2, 2, 2, 1.
The minimum of these values are 1 thus the answer is 1.

The best answer I came up with is of complexity O(n log k). What I do is to create a binary search tree with the first k elements, get the maximum value in the tree and save it in variable minOfMax, then loop one element at a time with the remaining elements in the array, remove the first element in the previous segment from the binary search tree, insert the last element of the new segment in the tree, get the maximum element in the tree and compare it with minOfMax leaving in minOfMax the min value of the two.

The ideal answer needs to be of complexity O(n). Thank you.

Answer 1

There is a very clever way to do this that's related to this earlier question. The idea is that it's possible to build a queue data structure that supports enqueue, dequeue, and find-max in amortized O(1) time (there are many ways to do this; two are explained in the original question). Once you have this data structure, begin by adding the first k elements from the array into the queue in O(k) time. Since the queue supports O(1) find-max, you can find the maximum of these k elements in O(1) time. Then, continuously dequeue an element from the queue and enqueue (in O(1) time) the next array element. You can then query in O(1) what the maximum of each of these k-element subarrays are. If you track the minimum of these values that you see over the course of the array, then you have an O(n)-time, O(k)-space algorithm for finding the minimum maximum of the k-element subarrays.

Hope this helps!

Answer 2

@templatetypedef's answer works, but I think I have a more direct approach.

Start by computing the max for the following (closed) intervals:

[k-1, k-1]
[k-2, k-1]
[k-3, k-1]
...
[0, k-1]

Note that each of these can be computed in constant time from the preceeding one.

Next, compute the max for these intervals:

[k, k]
[k, k+1]
[k, k+2]
...
[k, 2k-1]

Now these intervals:

[2k-1, 2k-1]
[2k-2, 2k-1]
[2k-3, 2k-1]
...
[k+1, 2k-1]

Next you do the intervals from 2k to 3k-1 ("forwards intervals"), then from 3k-1 down to 2k+1 ("backwards intervals"). And so on until you reach the end of the array.

Put all of these into a big table. Note that each entry in this table took constant time to compute. Observe that there are at most 2*n intervals in the table (because each element appears once on the right side of a "forwards interval" and once on the left side of a "backwards interval").

Now, if [a,b] is any interval of width k, it must contain exactly one of 0, k, 2k, ...

Say it contains m*k.

Observe that the intervals [a, m*k-1] and [m*k ,b] are both somewhere in our table. So we can simply look up the max for each, and the max of those two values is the max of the interval [a,b].

So for any interval of width k, we can use our table to get its maximum in constant time. We can generate the table in O(n) time. Result follows.

Answer 3

I implemented (and commented) templatetypedef's answer in C#.

n is array length, k is window size.

    public static void printKMax(int[] arr, int n, int k)
    {
        Deque<int> qi = new Deque<int>(); 
        int i;

        for (i=0 ; i < k ; i++) // The first window of the array
        {
            while ((qi.Count > 0) && (arr[i] >= arr[qi.PeekBack()]))
            {
                qi.PopBack();
            }
            qi.PushBack(i);
        }

        for(i=k ; i < n ; ++i)
        {
            Console.WriteLine(arr[qi.PeekFront()]); // the first item is the largest element in previous window. The second item is its index.

            while (qi.Count > 0 && qi.PeekFront() <= i - k) 
            {
                qi.PopFront(); //When it's out of its window k 
            }
            while (qi.Count>0 && arr[i] >= arr[qi.PeekBack()]) 
            {
                qi.PopBack();
            }
            qi.PushBack(i);
        }
        Console.WriteLine(arr[qi.PeekFront()]);
    }