Maximum of minimums of every window size in a given array Hard 0 attempts
GeeksforGeeks ↗

Maximum of minimums of every window size in a given array

Hard Stack&Queue GeeksforGeeks

You're given an integer array of size n. For every window size w from 1 up to n, look at all contiguous subarrays of that length, take the minimum value within each one, and then report the largest of those minimums. Do this for every window size and return the full set of results.

Input Format
Implement maximumOfMinimumsOfEveryWindowSizeInAGivenArray(arr). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
arr = [10,20,30,50,10,70,30]
Output
[70,30,20,10,10,10,10]

Example 2

Input
arr = [-1,-2,-3]
Output
[-1,-2,-3]
Constraints
  • 1 <= arr.length <= 10^5
  • -10^9 <= arr[i] <= 10^9
Test Cases (2)
Case 1
Args: [[10,20,30,50,10,70,30]] Expected: [70,30,20,10,10,10,10]
Case 2
Args: [[-1,-2,-3]] Expected: [-1,-2,-3]
Topics
Stack&Queue

Approach: Stack-based with Next/Prev Smaller

For each element, compute the range where it is the minimum using next-smaller and prev-smaller stacks. That element is the answer for a window of that range length. Fill remaining positions from right to left.

javascript
function maximumOfMinimumsOfEveryWindowSizeInAGivenArray(arr) {
  const n = arr.length;
  const left = new Array(n), right = new Array(n), stack = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && arr[stack[stack.length-1]] >= arr[i]) stack.pop();
    left[i] = stack.length ? stack[stack.length-1] : -1;
    stack.push(i);
  }
  stack.length = 0;
  for (let i = n-1; i >= 0; i--) {
    while (stack.length && arr[stack[stack.length-1]] >= arr[i]) stack.pop();
    right[i] = stack.length ? stack[stack.length-1] : n;
    stack.push(i);
  }
  const result = new Array(n + 1).fill(-Infinity);
  for (let i = 0; i < n; i++) {
    const len = right[i] - left[i] - 1;
    result[len] = Math.max(result[len], arr[i]);
  }
  for (let i = n-1; i >= 1; i--) result[i] = Math.max(result[i], result[i+1]);
  return result.slice(1);
}

Time Complexity: O(n)

Space Complexity: O(n)

Saved in this browser only. Private to you.

JavaScript