Maximum of Minimum for Every Window Size

Hard
1417.

Maximum of Minimum for Every Window Size

Maximum of Minimum for Every Window Size is a hard coding problem on arrays, stack and sliding window, asked in Amazon, Microsoft and Flipkart interviews.

For every window size k from 1 to n, look at all n - k + 1 contiguous windows of arr of that size, take the minimum of each window, and then the maximum of those minimums.

Return an array res of length n where res[k - 1] is that value for window size k.

Example 1

Input
arr = [3,8,5,1,6]
Output
[8,5,3,1,1]
Explanation
Size 2: the windows' minimums are 3, 5, 1, 1 — the largest is 5. Size 3: 3, 1, 1 — the largest is 3.

Example 2

Input
arr = [4,4,4]
Output
[4,4,4]

Example 3

Input
arr = [2,9,9,2,7]
Output
[9,9,2,2,2]

Constraints

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number[]}
 */
var maxOfMins = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum of Minimum for Every Window Size — Solution

Maximum of Minimum for Every Window Size solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Maximum of Minimum for Every Window Size is a hard coding problem on arrays, stack and sliding window, asked in Amazon, Microsoft and Flipkart interviews.

Problem statement

For every window size k from 1 to n, look at all n - k + 1 contiguous windows of arr of that size, take the minimum of each window, and then the maximum of those minimums.

Return an array res of length n where res[k - 1] is that value for window size k.

Example 1

Input: arr = [3,8,5,1,6]
Output: [8,5,3,1,1]
Explanation: Size 2: the windows' minimums are 3, 5, 1, 1 — the largest is 5. Size 3: 3, 1, 1 — the largest is 3.

Example 2

Input: arr = [4,4,4]
Output: [4,4,4]

Example 3

Input: arr = [2,9,9,2,7]
Output: [9,9,2,2,2]

Constraints

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^6

Hints for Maximum of Minimum for Every Window Size

  1. Hint 1

    Turn it around: for each element, what is the largest window in which it is the minimum?

  2. Hint 2

    That window stretches from just after the previous smaller element to just before the next smaller element — a monotonic stack gives both in O(n).

  3. Hint 3

    If arr[i] is the minimum of a window of length L, it is a candidate for size L and also for every smaller size (shrink the window around it). Record the best per exact length, then sweep from long to short taking running maximums.

How to solve Maximum of Minimum for Every Window Size

Each element is the minimum of exactly one maximal window. Recording its value at that window's length, then propagating maximums from longer to shorter lengths, answers every size at once.

Approach

  1. With a monotonic stack compute left[i] (previous index with a smaller value, or -1) and right[i] (next index with a smaller-or-equal value, or n).
  2. The length L = right[i] - left[i] - 1 window has arr[i] as its minimum; set best[L] = max(best[L], arr[i]).
  3. For L from n - 1 down to 1, set best[L] = max(best[L], best[L + 1]).
  4. Return best[1..n].

Why it works

The answer for size k is some window minimum arr[i]. That element's maximal window has length >= k, and any length-k sub-window containing i still has minimum arr[i], so the value is achievable for size k — which is what the backward sweep propagates. Conversely every recorded value is a real window minimum. With equal values, stopping at a smaller-or-equal element on the right only shortens the windows of earlier copies; the last copy still gets the full length.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The answers are non-increasing in k; forgetting the backward sweep leaves sizes that no element 'owns' at their initial value.
  • Window length is right - left - 1, with the sentinels -1 and n.
  • The brute-force O(n²) double loop is fine for small inputs but not for 10^5.

Reference solution

Python

from typing import List

def maxOfMins(arr: List[int]) -> List[int]:
    n = len(arr)
    left = [-1] * n
    right = [n] * n
    st = []
    for i in range(n):
        while st and arr[st[-1]] >= arr[i]:
            right[st.pop()] = i
        left[i] = st[-1] if st else -1
        st.append(i)
    best = [0] * (n + 2)
    for i in range(n):
        length = right[i] - left[i] - 1
        best[length] = max(best[length], arr[i])
    for length in range(n - 1, 0, -1):
        best[length] = max(best[length], best[length + 1])
    return best[1:n + 1]

Java

public static int[] maxOfMins(int[] arr) {
    int n = arr.length;
    int[] left = new int[n], right = new int[n], st = new int[n];
    int top = 0;
    for (int i = 0; i < n; i++) {
        right[i] = n;
        while (top > 0 && arr[st[top - 1]] >= arr[i]) right[st[--top]] = i;
        left[i] = top > 0 ? st[top - 1] : -1;
        st[top++] = i;
    }
    int[] best = new int[n + 2];
    for (int i = 0; i < n; i++) {
        int len = right[i] - left[i] - 1;
        best[len] = Math.max(best[len], arr[i]);
    }
    for (int k = n - 1; k >= 1; k--) best[k] = Math.max(best[k], best[k + 1]);
    return Arrays.copyOfRange(best, 1, n + 1);
}

C++

vector<int> maxOfMins(vector<int>& arr) {
    int n = arr.size();
    vector<int> left(n, -1), right(n, n), st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[st.back()] >= arr[i]) {
            right[st.back()] = i;
            st.pop_back();
        }
        left[i] = st.empty() ? -1 : st.back();
        st.push_back(i);
    }
    vector<int> best(n + 2, 0);
    for (int i = 0; i < n; i++) {
        int len = right[i] - left[i] - 1;
        best[len] = max(best[len], arr[i]);
    }
    for (int k = n - 1; k >= 1; k--) best[k] = max(best[k], best[k + 1]);
    return vector<int>(best.begin() + 1, best.begin() + n + 1);
}

JavaScript

var maxOfMins = function(arr) {
    var n = arr.length;
    var left = new Array(n).fill(-1), right = new Array(n).fill(n), st = [];
    for (var i = 0; i < n; i++) {
        while (st.length > 0 && arr[st[st.length - 1]] >= arr[i]) right[st.pop()] = i;
        left[i] = st.length > 0 ? st[st.length - 1] : -1;
        st.push(i);
    }
    var best = new Array(n + 2).fill(0);
    for (var j = 0; j < n; j++) {
        var len = right[j] - left[j] - 1;
        if (arr[j] > best[len]) best[len] = arr[j];
    }
    for (var k = n - 1; k >= 1; k--) if (best[k + 1] > best[k]) best[k] = best[k + 1];
    return best.slice(1, n + 1);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Stack Data Structure