Problem: Given an integer array of size n, find the maximum of the minimum’s of every window size in the array.
For example:
Method 2: If we work bit hard, we can come out with O(n) algorithm. The idea is to use auxiliary for pre-proccessing.
1. Find indexes of next smaller and previous smaller for every element.
For example:
Input: arr[] = {10, 20, 30, 50, 10, 70, 30}
Output: 7 3 2 1 1 1 1
First element in output indicates maximum of minimums of all
windows of size 1.
Minimums of windows of size 1 are {1}, {2}, {3}, {5}, {1},
{7} and {3}. Maximum of these minimums is 7
Second element in output indicates maximum of minimums of all
windows of size 2.
Minimums of windows of size 2 are {1}, {2}, {3}, {1}, {1},
and {3}. Maximum of these minimums is 3
Third element in output indicates maximum of minimums of all
windows of size 3.
Minimums of windows of size 3 are {1}, {2}, {1}, {1} and {1}.
Maximum of these minimums is 2
Similarly other elements of output are computed.
Method 1: The brute-force is to consider sub-array of all size and then find the maximum of all sub-arrays.
class practice
{
/* method to print the required result */
static void printMaxOfMin(int arr[], int n)
{
/* Consider all windows of different sizes starting
from size 1 */
for (int k=1; k<=n; k++)
{
/* initialize max of min for current window size k */
int maxOfMin = arr[0];
/* traverse through all windows of current size k */
for (int i = 0; i <= n-k; i++)
{
/* Finding minimum of current window */
int min = arr[i];
for (int j = 1; j < k; j++)
{
if (arr[i+j] < min)
min = arr[i+j];
}
/* Update maxOfMin if required */
if (min > maxOfMin)
maxOfMin = min;
}
/* Print max of min for current window size */
System.out.print(maxOfMin + " ");
}
}
/* driver method */
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 5, 1, 7, 3};
printMaxOfMin(arr, arr.length);
}
}
Output:
7 3 2 1 1 1 1Time Complexity: O(n3) and Space Complexity: O(1)
Method 2: If we work bit hard, we can come out with O(n) algorithm. The idea is to use auxiliary for pre-proccessing.
Next smaller: is the nearest smallest element on right side of arr[i].
Similarly, Previous smaller: is the nearest smallest element on left side of arr[i].
If there is no smaller element on right side, then next smaller is n.If there is no smaller on left side, then previous smaller is -1.
For input {10, 20, 30, 50, 10, 70, 30}, array of indexes of next smaller is {7, 4, 4, 4, 7, 6, 7} and array of indexes of previous smaller is {-1, 0, 1, 2, -1, 4, 4}.
This step can be done in O(n). Refer this post.
2. Once we have indexes of next and previous smaller, we know that arr[i] is a minimum of a window of length “right[i] – left[i] – 1”. Lengths of windows for which the elements are minimum are {7, 3, 2, 1, 7, 1, 2}. This array indicates, first element is minimum in window of size 7, second element is minimum in window of size 3, and so on.
Create an auxiliary array ans[n+1] to store the result. Values in ans[] can be filled by iterating through right[] and left[]
for (int i=0; i < n; i++)
{
// length of the interval
int len = right[i] - left[i] - 1;
// a[i] is the possible answer for
// this length len interval
ans[len] = max(ans[len], arr[i]);
}
We get the ans[] array as {0, 70, 30, 20, 0, 0, 0, 10}. Note that ans[0] or answer for length 0 is useless.
3. Some entries in ans[] are 0 and yet to be filled. For example, we know maximum of minimum for lengths 1, 2, 3 and 7 are 70, 30, 20 and 10 respectively, but we don’t know the same for lengths 4, 5 and 6.
Below are few important observations to fill remaining entries
a) Result for length i, i.e. ans[i] would always be greater or same as result for length i+1, i.e., ans[i+1].
b) If ans[i] is not filled it means there is no direct element which is minimum of length i and therefore either the element of length ans[i+1], or ans[i+2], and so on is same as ans[i]
So we fill rest of the entries using below loop.
for (int i=n-1; i>=1; i--)
ans[i] = max(ans[i], ans[i+1]);
Below is implementation of above algorithm.import java.util.Stack;
class practice
{
/* method to print the required result */
static void printMaxOfMin(int arr[], int n)
{
/* used to find previous and next smaller */
Stack s = new Stack<>();
/* Arrays to store previous and next smaller */
int left[] = new int[n+1];
int right[] = new int[n+1];
/* Initialize elements of left[] and right[] */
for (int i=0; i= arr[i])
s.pop();
if (!s.empty())
left[i] = s.peek();
s.push(i);
}
/* use same stack for right[] */
while (!s.empty())
s.pop();
/* filling the right[] array */
for (int i = n-1 ; i>=0 ; i-- )
{
while (!s.empty() && arr[s.peek()] >= arr[i])
s.pop();
if(!s.empty())
right[i] = s.peek();
s.push(i);
}
/* initial answer array */
int ans[] = new int[n+1];
for (int i=0; i<=n; i++)
ans[i] = 0;
/* Fill answer array by comparing minimums of all
lengths computed using left[] and right[] */
for (int i=0; i=1; i--)
ans[i] = Math.max(ans[i], ans[i+1]);
/* printing result */
for (int i=1; i<=n; i++)
System.out.print(ans[i] + " ");
}
/* driver function */
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 5, 1, 7, 3};
printMaxOfMin(arr, arr.length);
}
}
Output:
7 3 2 1 1 1 1Time Complexity: O(n) and Space Complexity: O(2*n)