Problem Description

Given an array of integers arr of length n, you are to determine, for every possible subarray length k (where 1 ≤ k ≤ n), the maximum value among the minimums of all subarrays of length k. In other words, for each possible window size k, find the largest number that is the smallest element in some subarray of length k.

• Each subarray consists of consecutive elements of arr.
• For every k from 1 to n, report a value res[k-1] which is the maximum of all minimums of all subarrays of length k.
• Return an array res of length n such that res[i] is the answer for window size i+1.

Constraints:

• 1 ≤ n ≤ 10^5
• 1 ≤ arr[i] ≤ 10^6

Thought Process

The naive way to solve this problem is to consider every subarray of every length, compute its minimum, and then find the maximum among those minimums for each length. But this brute-force approach is too slow for large arrays, as it would require checking O(n^2) subarrays.

To optimize, we need to quickly find, for each possible window size, the largest value that can be the minimum in any subarray of that size. This suggests we should, for each element, determine the largest window in which it is the minimum, and then use this information to update the result for that window size.

The key insight is to use monotonic stacks to efficiently find the previous and next smaller elements for each position, which in turn tells us the window size where each element is the minimum.

Solution Approach

We solve the problem in the following steps:

1. Find Previous and Next Smaller Elements:
   • For each element in arr, use a stack to find the index of the previous smaller element to its left.
   • Similarly, find the next smaller element to its right.
   • If there is no smaller element on one side, use -1 (for left) or n (for right) as a sentinel value.
2. Determine the Maximum Window Size for Each Element:
   • The window in which arr[i] is the minimum is from prev_smaller[i] + 1 to next_smaller[i] - 1.
   • The length of this window is len = next_smaller[i] - prev_smaller[i] - 1.
3. Fill the Result Array:
   • For each arr[i], update res[len - 1] to be the maximum of its current value and arr[i].
4. Propagate Maximums Backwards:
   • Since a window of size k is contained within all larger window sizes, propagate the maximums backwards so that res[k-1] ≥ res[k] for all k.

This approach ensures we only need to traverse the array a few times, leading to an efficient solution.

Example Walkthrough

Let's consider arr = [1, 2, 3, 2, 1].

1. Find previous and next smaller for each element:
   • For arr[0] = 1: prev = -1, next = 4
   • For arr[1] = 2: prev = 0, next = 4
   • For arr[2] = 3: prev = 1, next = 3
   • For arr[3] = 2: prev = 0, next = 4
   • For arr[4] = 1: prev = -1, next = 5
2. Window lengths where each is minimum:
   • arr[0]: len = 4 - (-1) - 1 = 4
   • arr[1]: len = 4 - 0 - 1 = 3
   • arr[2]: len = 3 - 1 - 1 = 1
   • arr[3]: len = 4 - 0 - 1 = 3
   • arr[4]: len = 5 - (-1) - 1 = 5
3. Fill result array:
   • res[3] = max(res[3], arr[0]) = max(-inf, 1) = 1
   • res[2] = max(res[2], arr[1]) = max(-inf, 2) = 2
   • res[0] = max(res[0], arr[2]) = max(-inf, 3) = 3
   • res[2] = max(res[2], arr[3]) = max(2, 2) = 2
   • res[4] = max(res[4], arr[4]) = max(-inf, 1) = 1
4. Propagate maximums backwards:
   • res[3] = max(res[3], res[4]) = max(1, 1) = 1
   • res[2] = max(res[2], res[3]) = max(2, 1) = 2
   • res[1] = max(res[1], res[2]) = max(-inf, 2) = 2
   • res[0] = max(res[0], res[1]) = max(3, 2) = 3
5. Final result: [3, 2, 2, 1, 1]

Time and Space Complexity

• Brute-force approach:
  • Time: O(n^2) (checking all subarrays for all lengths)
  • Space: O(n) (to store results)
• Optimized approach (using stacks):
  • Time: O(n) (each element is pushed and popped at most once from the stack)
  • Space: O(n) (for stacks and result array)

The optimized solution is efficient and suitable for large arrays.

Summary

To solve the Maximum of Minimum Values in All Subarrays problem, we use monotonic stacks to efficiently find the largest window where each element is the minimum. By mapping each element to the window size it can dominate, and then propagating maximums, we produce the correct result for all window sizes in linear time. This technique is a powerful example of how stack-based approaches can optimize sliding window and range query problems.

Code Implementation

def maxOfMin(arr):
    n = len(arr)
    res = [float('-inf')] * n

    # Previous and next smaller elements
    prev = [-1] * n
    next_ = [n] * n
    stack = []

    # Previous smaller
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        prev[i] = stack[-1] if stack else -1
        stack.append(i)

    stack = []
    # Next smaller
    for i in range(n-1, -1, -1):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        next_[i] = stack[-1] if stack else n
        stack.append(i)

    # Fill result for lengths
    for i in range(n):
        length = next_[i] - prev[i] - 1
        res[length-1] = max(res[length-1], arr[i])

    # Propagate max backwards
    for i in range(n-2, -1, -1):
        res[i] = max(res[i], res[i+1])

    return res
      

#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

vector<int> maxOfMin(vector<int>& arr) {
    int n = arr.size();
    vector<int> res(n, INT_MIN);
    vector<int> prev(n, -1), next(n, n);
    stack<int> st;

    // Previous smaller
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && arr[st.top()] >= arr[i])
            st.pop();
        prev[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();

    // Next smaller
    for (int i = n-1; i >= 0; --i) {
        while (!st.empty() && arr[st.top()] >= arr[i])
            st.pop();
        next[i] = st.empty() ? n : st.top();
        st.push(i);
    }

    // Fill result for lengths
    for (int i = 0; i < n; ++i) {
        int len = next[i] - prev[i] - 1;
        res[len-1] = max(res[len-1], arr[i]);
    }

    // Propagate max backwards
    for (int i = n-2; i >= 0; --i)
        res[i] = max(res[i], res[i+1]);
    return res;
}
      

import java.util.*;

public class Solution {
    public int[] maxOfMin(int[] arr) {
        int n = arr.length;
        int[] res = new int[n];
        Arrays.fill(res, Integer.MIN_VALUE);
        int[] prev = new int[n];
        int[] next = new int[n];
        Stack<Integer> stack = new Stack<>();

        // Previous smaller
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i])
                stack.pop();
            prev[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        stack.clear();

        // Next smaller
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i])
                stack.pop();
            next[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        // Fill result for lengths
        for (int i = 0; i < n; i++) {
            int len = next[i] - prev[i] - 1;
            res[len - 1] = Math.max(res[len - 1], arr[i]);
        }

        // Propagate max backwards
        for (int i = n - 2; i >= 0; i--)
            res[i] = Math.max(res[i], res[i + 1]);
        return res;
    }
}
      

function maxOfMin(arr) {
    const n = arr.length;
    const res = Array(n).fill(-Infinity);
    const prev = Array(n).fill(-1);
    const next = Array(n).fill(n);
    const stack = [];

    // Previous smaller
    for (let i = 0; i < n; i++) {
        while (stack.length && arr[stack[stack.length-1]] >= arr[i]) {
            stack.pop();
        }
        prev[i] = stack.length ? stack[stack.length-1] : -1;
        stack.push(i);
    }

    stack.length = 0;
    // Next smaller
    for (let i = n-1; i >= 0; i--) {
        while (stack.length && arr[stack[stack.length-1]] >= arr[i]) {
            stack.pop();
        }
        next[i] = stack.length ? stack[stack.length-1] : n;
        stack.push(i);
    }

    // Fill result for lengths
    for (let i = 0; i < n; i++) {
        let len = next[i] - prev[i] - 1;
        res[len-1] = Math.max(res[len-1], arr[i]);
    }

    // Propagate max backwards
    for (let i = n-2; i >= 0; i--) {
        res[i] = Math.max(res[i], res[i+1]);
    }
    return res;
}