Maximum of Minimum Values in All Subarrays - Solution & Explanation

Problem Overview: Given an integer array, compute the maximum among the minimum values of all subarrays for every possible window size from 1 to n. For example, among all subarrays of size k, find their minimum values and report the largest of those minimums. The result is an array of length n.

Approach 1: Brute Force Window Enumeration (O(n^3) time, O(1) space)

Enumerate every possible subarray size k. For each size, slide a window across the array and compute the minimum value inside that window. Track the maximum among those minimums. Computing the minimum for each window requires scanning up to k elements, which makes the total complexity cubic in the worst case. This approach is useful for understanding the problem definition but becomes impractical once the array grows beyond a few thousand elements.

Approach 2: Expand Each Minimum Using Monotonic Stack (O(n) time, O(n) space)

The key observation: instead of iterating over window sizes, determine the largest window where each element acts as the minimum. Use a monotonic stack to compute the previous smaller and next smaller element for every index. These boundaries define the span where arr[i] is the smallest value. If the distance between those boundaries is len, then arr[i] can serve as the minimum for a window of size len. Update result[len] with max(result[len], arr[i]). After processing all elements, propagate values backward so smaller windows inherit the best values from larger windows.

This approach converts a window enumeration problem into a boundary discovery problem. The stack maintains indices in increasing order of values while scanning the array. Each element is pushed and popped at most once, giving linear time complexity. The method relies heavily on patterns common in stack and array problems, particularly those involving nearest smaller elements.

Recommended for interviews: Interviewers expect the monotonic stack solution. A brute force explanation shows you understand the problem definition, but the optimal O(n) approach demonstrates familiarity with nearest-smaller-element patterns and span calculations, which frequently appear in advanced array and stack questions.