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

Given an integer array of size n, find the maximum of the minimums for every window size from 1 to n. For each window size w, consider all contiguous subarrays of that size, find the minimum of each, and take the maximum among those minimums.

Example:

Input: arr = [10, 20, 30, 50, 10, 70, 30]
Output: [70, 30, 20, 10, 10, 10, 10]
Sample Input
—
Sample Output
—
Constraints
  • 1 <= N <= 10^5
Test Cases
Case 1
Args: [[10,20,30,50,10,70,30]] Expected: [70,30,20,10,10,10,10]
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.

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(0);
  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