Find the maximum value of minimum of each subarray of non fixed length x where 1<= x <= N

Question

Interview Question:

You are given N numbers in an array. A group of a numbers is a non-empty contiguous segment of array. The size of a group is the number of numbers in that group.

Let A be the minimum number in a group. The task is to find for each x (1 <= x <= N), the maximum value of A among all groups of size x.

For example, if N = 3 and the array is [1,2,3], then the answer will be 3 (x = 1), 2 (x = 2), 1 (x = 3).

Numbers can be repeated in the array (For example, for N = 7, the array can be [1,2,3,4,5,4,6].

For explication, the following C code is a naive solution:

#include <stdio.h>

int main() {
    int a[] = {6,1,3,2,5,4,7};
    size_t N = sizeof a / sizeof *a;

    for (size_t i=0; i<N; ++i) printf("%d ", a[i]); puts("\n");

    size_t group_size, start, i;
    int max, min;
    for (group_size = 1; group_size <= N; ++group_size) {
        max = 0;
        for (start = 0; start <= N - group_size; ++start) {
            min = a[start];
            for (i = start + 1; i < start + group_size; ++i) {
                if (a[i] < min)
                    min = a[i];
            }
            if (min > max)
                max = min;
        }
        printf("%d ", max);
    }

    return 0;
}

Output:

6 1 3 2 5 4 7

7 4 4 2 2 1 1

Answer 1

Very brief sketch of a linear-time solution: for each array element, compute the size of the maximal group for which that element is the minimum. (Break ties by treating the first of two equal elements as lesser.) Sort the elements by their associated size, in linear time using a degenerate bucket sort. Scan the elements by size large to small, outputting the maximum element seen so far (i.e., the maximum element whose group size meets the current threshold).

The tricky step is computing the group sizes. We keep a stack and scan the array beginning to end. For each element, we pop the stack elements greater than it, thereby ending their groups. Here's a trace on 6 1 3 2 5 4 7.

stack: (-inf @ -1)  {sentinel}

6 1 3 2 5 4 7 -inf  {sentinel}
^
stack: (-inf @ -1), (6 @ 0)

6 1 3 2 5 4 7 -inf
  ^
pop (6 @ 0): group size of 6 is (1 - (-1)) - 1 = 1
stack: (-inf @ -1), (1 @ 1)

6 1 3 2 5 4 7 -inf
    ^
stack: (-inf @ -1), (1 @ 1), (3 @ 2)

6 1 3 2 5 4 7 -inf
      ^
pop (3 @ 2): group size of 3 is (3 - 1) - 1 = 1
stack: (-inf @ -1), (1 @ 1), (2 @ 3)

6 1 3 2 5 4 7 -inf
        ^
stack: (-inf @ -1), (1 @ 1), (2 @ 3), (5 @ 4)

6 1 3 2 5 4 7 -inf
          ^
pop (5 @ 4): group size of 5 is (5 - 3) - 1 = 1
stack: (-inf @ -1), (1 @ 1), (2 @ 3), (4 @ 5)

6 1 3 2 5 4 7 -inf
            ^
stack: (-inf @ -1), (1 @ 1), (2 @ 3), (4 @ 5), (7 @ 6)

6 1 3 2 5 4 7 -inf
              ^
pop (7 @ 6): group size of 7 is (7 - 5) - 1 = 1
pop (4 @ 5): group size of 4 is (7 - 3) - 1 = 3
pop (2 @ 3): group size of 2 is (7 - 1) - 1 = 5
pop (1 @ 1): group size of 1 is (7 - (-1)) - 1 = 7
stack: (-inf @ -1), (inf @ 7)

Answer 2

Here is an O(n²) solution.

Set the output array to empty and the input array a to the initial values.

While a is non empty:

• Calculate the max value of a an add to start of the output array
• Perform a shrinking operation on a where each element a[i] is set to the minimum of a[i] and a[i+1], and the last element is removed

Example:

output = []
a = [1,2,3,4,5,4,6]
output = [6] // add max of a to start of output array
a = [1,2,3,4,4,4]  // shrink array
output = [4,6] // add max of a to start of output array
a = [1,2,3,4,4]  // shrink array
output = [4,4,6] // add max of a to start of output array
a = [1,2,3,4]  // shrink array
output = [4,4,4,6] // add max of a to start of output array
a = [1,2,3]  // shrink array
output = [3,4,4,4,6] // add max of a to start of output array
a = [1,2]  // shrink array
output = [2,3,4,4,4,6] // add max of a to start of output array
a = [1]  // shrink array
output = [1,2,3,4,4,4,6] // add max of a to start of output array
a = []

At the beginning of the first iteration of the loop, a will contain the minimum of all groups of length 1 (just the initial values). At the start of the 2nd iteration it will contain the minimum of all groups of length 2, and so on.

At each iteration, the minimum of elements a[i] to a[j] (min(a[i]...a[j])) will be equal to

min(min(a[i]...a[j-1]),min(a[i+1]...a[j]))

so you can compute the minimums for groups of length n based on adjacent groups of length n-1.

C code:

#include <stdio.h>

int main() {
    int a[] = {6,1,3,2,5,4,7};
    size_t i, N = sizeof a / sizeof *a;

    for (i=0; i<N; ++i) printf("%d ", a[i]); puts("\n");

    while(N > 0)
    {
        int max = a[0];
        for(i = 0; i < N - 1; i++)
        {
            if(a[i+1] > max)
               max = a[i+1];
            a[i] = a[i+1] < a[i] ? a[i+1] : a[i];
        }
        printf("%d ", max);
        N--;
    }

    return 0;
}

Demo

Answer 3

This question is just using fancy words. All you need to calculate is the (x - 1)th maximum number in a reverse sorted array.

To see this, suppose you have an array of the form:

A = [12, 14, 26, 50, 43];

If you sort it, it will become

A' = [12, 14, 26, 43, 50];

Now, any subarray which needs to maximize the minimum value, will be the subarray of length x when started from the end. Because for all other possible subarrays, elements smaller than the xth element from end will have to be there, thereby reducing the minimum value.

So to get your answer, you just reverse sort your array and the element at index (x - 1) is your answer.

A'' = [50, 43, 26, 14, 12]

The maximum value of minimum of each subarray of non fixed length x can be calculated easily.

EDIT:

For example see for x from 1 to 3

 Length 1: 50
 Length 2: 43
 Length 3: 26

and so on.

EDIT2:

This will only work if all the elements are unique.