Maximum of Minimum Values in All Subarrays

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 + 1 of the array nums.
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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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.length
1 <= n <= 10^5
0 <= 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


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.

Problem#

Examples#

Solution#

Method 1 – Monotonic Stack for Window Minimums#

Intuition#

Approach#

Code#

Complexity#