Maximum of Minimum Values in All Subarrays
MediumUpdated: Aug 2, 2025
Practice on:
Problem
You are given an integer array nums of size n. You are asked to solve n
queries for each integer i in the range 0 <= i < n.
To solve the ith query:
- Find the minimum value in each possible subarray of size
i + 1of the arraynums. - Find the maximum of those minimum values. This maximum is the answer to the query.
Return a0-indexed integer array ans of sizen such thatans[i]
is the answer to theith query.
A subarray is a contiguous sequence of elements in an array.
Examples
Example 1:
Input: nums = [0,1,2,4]
Output: [4,2,1,0]
Explanation:
i=0:
- The subarrays of size 1 are [0], [1], [2], [4]. The minimum values are 0, 1, 2, 4.
- The maximum of the minimum values is 4.
i=1:
- The subarrays of size 2 are [0,1], [1,2], [2,4]. The minimum values are 0, 1, 2.
- The maximum of the minimum values is 2.
i=2:
- The subarrays of size 3 are [0,1,2], [1,2,4]. The minimum values are 0, 1.
- The maximum of the minimum values is 1.
i=3:
- There is one subarray of size 4, which is [0,1,2,4]. The minimum value is 0.
- There is only one value, so the maximum is 0.
Example 2:
Input: nums = [10,20,50,10]
Output: [50,20,10,10]
Explanation:
i=0:
- The subarrays of size 1 are [10], [20], [50], [10]. The minimum values are 10, 20, 50, 10.
- The maximum of the minimum values is 50.
i=1:
- The subarrays of size 2 are [10,20], [20,50], [50,10]. The minimum values are 10, 20, 10.
- The maximum of the minimum values is 20.
i=2:
- The subarrays of size 3 are [10,20,50], [20,50,10]. The minimum values are 10, 10.
- The maximum of the minimum values is 10.
i=3:
- There is one subarray of size 4, which is [10,20,50,10]. The minimum value is 10.
- There is only one value, so the maximum is 10.
Constraints:
n == nums.length1 <= n <= 10^50 <= nums[i] <= 10^9
Solution
Method 1 – Monotonic Stack for Window Minimums
Intuition
For each window size, the answer is the maximum of all minimums of subarrays of that size. We can use a monotonic stack to efficiently find, for each element, the largest window in which it is the minimum, and then fill the answer array accordingly.
Approach
- For each element, find the index of the previous and next smaller elements using a monotonic stack.
- The length of the window where the current element is the minimum is
right[i] - left[i] - 1. - For each window size, keep the maximum of the minimums found for that size.
- Fill the answer array from the back to ensure all smaller window sizes are at least as large as the next bigger window size.
- Return the answer array.
Code
C++
class Solution {
public:
vector<int> maxOfMin(int n, vector<int>& arr) {
vector<int> left(n, -1), right(n, n), ans(n, INT_MIN);
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && arr[st.top()] >= arr[i]) st.pop();
if (!st.empty()) left[i] = st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && arr[st.top()] >= arr[i]) st.pop();
if (!st.empty()) right[i] = st.top();
st.push(i);
}
for (int i = 0; i < n; ++i) {
int len = right[i] - left[i] - 1;
ans[len - 1] = max(ans[len - 1], arr[i]);
}
for (int i = n - 2; i >= 0; --i) {
ans[i] = max(ans[i], ans[i + 1]);
}
return ans;
}
};
Go
func maxOfMin(arr []int) []int {
n := len(arr)
left := make([]int, n)
right := make([]int, n)
ans := make([]int, n)
for i := range left {
left[i] = -1
right[i] = n
ans[i] = -1 << 31
}
st := []int{}
for i := 0; i < n; i++ {
for len(st) > 0 && arr[st[len(st)-1]] >= arr[i] {
st = st[:len(st)-1]
}
if len(st) > 0 {
left[i] = st[len(st)-1]
}
st = append(st, i)
}
st = []int{}
for i := n - 1; i >= 0; i-- {
for len(st) > 0 && arr[st[len(st)-1]] >= arr[i] {
st = st[:len(st)-1]
}
if len(st) > 0 {
right[i] = st[len(st)-1]
}
st = append(st, i)
}
for i := 0; i < n; i++ {
l := right[i] - left[i] - 1
if arr[i] > ans[l-1] {
ans[l-1] = arr[i]
}
}
for i := n - 2; i >= 0; i-- {
if ans[i+1] > ans[i] {
ans[i] = ans[i+1]
}
}
return ans
}
Java
class Solution {
public int[] maxOfMin(int[] arr) {
int n = arr.length;
int[] left = new int[n], right = new int[n], ans = new int[n];
Arrays.fill(left, -1);
Arrays.fill(right, n);
Arrays.fill(ans, Integer.MIN_VALUE);
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && arr[st.peek()] >= arr[i]) st.pop();
if (!st.isEmpty()) left[i] = st.peek();
st.push(i);
}
st.clear();
for (int i = n - 1; i >= 0; i--) {
while (!st.isEmpty() && arr[st.peek()] >= arr[i]) st.pop();
if (!st.isEmpty()) right[i] = st.peek();
st.push(i);
}
for (int i = 0; i < n; i++) {
int len = right[i] - left[i] - 1;
ans[len - 1] = Math.max(ans[len - 1], arr[i]);
}
for (int i = n - 2; i >= 0; i--) {
ans[i] = Math.max(ans[i], ans[i + 1]);
}
return ans;
}
}
Kotlin
class Solution {
fun maxOfMin(arr: IntArray): IntArray {
val n = arr.size
val left = IntArray(n) { -1 }
val right = IntArray(n) { n }
val ans = IntArray(n) { Int.MIN_VALUE }
val st = ArrayDeque<Int>()
for (i in 0 until n) {
while (st.isNotEmpty() && arr[st.last()] >= arr[i]) st.removeLast()
if (st.isNotEmpty()) left[i] = st.last()
st.addLast(i)
}
st.clear()
for (i in n - 1 downTo 0) {
while (st.isNotEmpty() && arr[st.last()] >= arr[i]) st.removeLast()
if (st.isNotEmpty()) right[i] = st.last()
st.addLast(i)
}
for (i in 0 until n) {
val len = right[i] - left[i] - 1
ans[len - 1] = maxOf(ans[len - 1], arr[i])
}
for (i in n - 2 downTo 0) {
ans[i] = maxOf(ans[i], ans[i + 1])
}
return ans
}
}
Python
class Solution:
def maxOfMin(self, arr: list[int]) -> list[int]:
n = len(arr)
left = [-1] * n
right = [n] * n
ans = [float('-inf')] * n
st = []
for i in range(n):
while st and arr[st[-1]] >= arr[i]:
st.pop()
if st:
left[i] = st[-1]
st.append(i)
st.clear()
for i in range(n-1, -1, -1):
while st and arr[st[-1]] >= arr[i]:
st.pop()
if st:
right[i] = st[-1]
st.append(i)
for i in range(n):
l = right[i] - left[i] - 1
ans[l-1] = max(ans[l-1], arr[i])
for i in range(n-2, -1, -1):
ans[i] = max(ans[i], ans[i+1])
return ans
Rust
impl Solution {
pub fn max_of_min(arr: Vec<i32>) -> Vec<i32> {
let n = arr.len();
let mut left = vec![-1; n];
let mut right = vec![n as i32; n];
let mut ans = vec![i32::MIN; n];
let mut st = vec![];
for i in 0..n {
while let Some(&top) = st.last() {
if arr[top] >= arr[i] {
st.pop();
} else {
break;
}
}
if let Some(&top) = st.last() {
left[i] = top as i32;
}
st.push(i);
}
st.clear();
for i in (0..n).rev() {
while let Some(&top) = st.last() {
if arr[top] >= arr[i] {
st.pop();
} else {
break;
}
}
if let Some(&top) = st.last() {
right[i] = top as i32;
}
st.push(i);
}
for i in 0..n {
let len = right[i] - left[i] - 1;
ans[(len - 1) as usize] = ans[(len - 1) as usize].max(arr[i]);
}
for i in (0..n-1).rev() {
ans[i] = ans[i].max(ans[i+1]);
}
ans
}
}
TypeScript
class Solution {
maxOfMin(arr: number[]): number[] {
const n = arr.length;
const left = Array(n).fill(-1);
const right = Array(n).fill(n);
const ans = Array(n).fill(-Infinity);
const st: number[] = [];
for (let i = 0; i < n; i++) {
while (st.length && arr[st[st.length-1]] >= arr[i]) st.pop();
if (st.length) left[i] = st[st.length-1];
st.push(i);
}
st.length = 0;
for (let i = n-1; i >= 0; i--) {
while (st.length && arr[st[st.length-1]] >= arr[i]) st.pop();
if (st.length) right[i] = st[st.length-1];
st.push(i);
}
for (let i = 0; i < n; i++) {
const l = right[i] - left[i] - 1;
ans[l-1] = Math.max(ans[l-1], arr[i]);
}
for (let i = n-2; i >= 0; i--) {
ans[i] = Math.max(ans[i], ans[i+1]);
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n)— Each element is pushed and popped from the stack at most twice. - 🧺 Space complexity:
O(n)— For the stacks and answer arrays.