Interview Question:
You are given N number in an array. A group of a numbers is a non-empty contiguous segment of array.The size of group is the number of numbers in that group.
"A" is the minimum number in that group.Task was to find each x such that 1 <= x <= N the maximum value of "A" among all group of size x.
For example if N = 3 and number are 1,2,3 ,then the answer will be 3,2,1
Numbers can be repeated in the array like N=7 and numbers are =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
Best How To :
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)
