# 1950. Maximum of Minimum Values in All Subarrays

## Problem Description

The given problem involves an integer array `nums` of size `n`. We need to address `n` different queries indexed from 0 to `n-1`. For each query `i`, our task is to determine the maximum value out of the minimum values from all possible subarrays of size `i+1` within the array `nums`.

To make this clearer, let's consider the following steps for each query `i`:

1. Look at every subarray in `nums` that is exactly `i+1` elements long.
2. In each subarray, identify the smallest element.
3. Among these minimum values, find the largest one โ this will be the result for query `i`.

After solving all `n` queries, the result should be returned in a 0-indexed integer array `ans`, where `ans[i]` is the answer to the `i-th` query.

A subarray is defined as a contiguous sequence of elements within an array, which means you can take any start and end points within the array and all elements between those two points (inclusive) form a subarray.

## Intuition

The naive approach of solving this problem would be to consider each size of subarray and finding the maximum of minimum values explicitly. However, this approach would have a time complexity of O(n^3) which is inefficient for large arrays.

To optimize this, an approach is to leverage the Monotonic Stack data structure. The Monotonic Stack helps us to efficiently find the next greater or next smaller elements in an array in a linear time complexity. In this problem, we aim to construct two arrays `left` and `right`. For each element `nums[i]`:

• `left[i]` contains the index of the previous smaller element than `nums[i]`.
• `right[i]` contains the index of the next smaller element than `nums[i]`. If there is no such element, the default values are `-1` for `left[i]` and `n` for `right[i]`.

Once we have `left` and `right` arrays filled, for every index `i`, the width or the number of subarrays where `nums[i]` is the minimum can be calculated by `(right[i] - left[i] - 1)`. This width determines the position in the answer array `ans` which should be updated with `nums[i]` if it's larger than the existing value at that position in `ans`.

After finding the maximum minimum for each subarray size, the last step is to ensure each answer at index `i` in `ans` is at least as large as the answer at `i+1`. This is needed because if for a subarray of size `k`, the maximum minimum value was `v`, then for a subarray of size `(k-1)`, the maximum minimum cannot be less than `v`.

Overall, the main intuition is based on the observation that each element in the array could be the minimum for a certain range of subarray sizes, and we can use Monotonic Stacks to efficiently find out what those ranges are.

## Solution Approach

The implementation of the solution involves a single pass algorithm using the concept of Monotonic Stacks for finding the next smaller elements on both left and right sides for each element in the input array `nums`. This is essential in determining the maximum minimum for different subarray sizes.

Here's a step-by-step walkthrough of the solution:

1. Initialize two arrays `left` and `right` with lengths equal to that of `nums`. Set all values in `left` to `-1` and in `right` to `n`, where `n` is the size of `nums`. Also, create an empty list `stk` to be used as our Monotonic Stack.

2. Iterate through `nums` from left to right (using index `i`):

• Pop elements from the stack `stk` while the top of the stack is greater than or equal to the current element `nums[i]`.
• If `stk` is not empty after popping elements, it means `stk[-1]` is the previous smaller element's index, which we assign to `left[i]`.
• Push the current index `i` onto `stk`, indicating that we are considering `nums[i]` for the next elements' previous smaller check.
3. Reset the stack `stk` and perform a similar process from right to left (using a decreasing index `i`):

• Pop elements while the top of the stack is greater than or equal to `nums[i]`.
• If `stk` is not empty after the popping process, the top element of `stk` is the next smaller element's index, which we assign to `right[i]`.
• Push the current index `i` onto `stk`.
4. After constructing `left` and `right` arrays, initialize the answer array `ans` with zeros, with the same size as `nums`.

5. For every index `i` in `nums`, calculate the width `m` as the number of subarrays where `nums[i]` is the minimum by `right[i] - left[i] - 1`, and update `ans[m - 1]` with the maximum of its current value and `nums[i]`.

6. Iterate through `ans` in reverse (starting from second to last element), making sure each `ans[i]` is at least as large as `ans[i + 1]`. This step ensures the answers are correct and handle the case where a smaller subarray may have the same maximum minimum as a larger subarray.

By using the Monotonic Stack to track the bounds within which each element is the minimum value in subarrays, and by updating the answer array accordingly, the given solution efficiently resolves the problem with a time complexity of O(n), which is a significant improvement over the naive brute-force approach.

๐ช
Level Up Your
Algo Skills

### Example Walkthrough

Let's consider a small example with the integer array `nums = [3, 1, 2, 4]`. We will walk through the solution approach using the Monotonic Stack as described above.

1. Initialize arrays and stack:

• `left = [-1, -1, -1, -1]`
• `right = [4, 4, 4, 4]` (since `n = 4`)
• `stk = []` (empty stack)
2. Left smaller elements: Iterate from left to right.

• For `i = 0`: Stack is empty, so leave `left[0] = -1`. Push `0` to `stk`.
• For `i = 1`: Pop `0` because `nums[0] >= nums[1]`. Stack becomes empty, so leave `left[1] = -1`. Push `1` to `stk`.
• For `i = 2`: Stack's top element `1` is not greater than `nums[2]`, so leave `left[2] = 1`. Push `2` to `stk`.
• For `i = 3`: Stack's top element `2` is not greater than `nums[3]`, so leave `left[3] = 2`. Push `3` to `stk`.

At the end of this step:

• `left = [-1, -1, 1, 2]`
• Stack `stk` is reset to empty.
3. Right smaller elements: Iterate from right to left.

• For `i = 3`: Stack is empty, so leave `right[3] = 4`. Push `3` to `stk`.
• For `i = 2`: Stack's top element `3` is greater than `nums[2]`, so `right[2] = 3`. Push `2` to `stk`.
• For `i = 1`: Keep popping until `stk` is empty because `nums[3]` and `nums[2]` are greater. Now `right[1] = 4`. Push `1` to `stk`.
• For `i = 0`: `stk` top is `1`, and `nums[1]` is greater than `nums[0]`, so `right[0] = 1`. Push `0` to `stk`.

At the end of this step:

• `right = [1, 4, 3, 4]`
• Now we have both `left` and `right` filled out.

• `ans = [0, 0, 0, 0]`
5. Calculate and update `ans`:

• For `i = 0`: Width `m = right[0] - left[0] - 1 = 1`. Update `ans[0]` to `max(ans[0], nums[0]) = 3`.
• For `i = 1`: Width `m = right[1] - left[1] - 1 = 3`. Update `ans[2]` to `max(ans[2], nums[1]) = 1`.
• For `i = 2`: Width `m = right[2] - left[2] - 1 = 1`. Update `ans[0]` to `max(ans[0], nums[2]) = 3` (no change).
• For `i = 3`: Width `m = right[3] - left[3] - 1 = 1`. Update `ans[0]` to `max(ans[0], nums[3]) = 4`.

After this:

• `ans = [4, 0, 1, 0]`
6. Adjust `ans` in reverse:

• Iterate from `ans[2]` to `ans[0]`: Set `ans[i]` to `max(ans[i], ans[i + 1])`.
• After adjustment: `ans = [4, 2, 1, 0]` (Fill in the non-updated spots with the next greater values)

The final `ans` array represents the maximum value out of the minimum values of all possible subarrays for each subarray size. We conclude that the Monotonic Stack allows us to efficiently calculate these values.

## Python Solution

``````1from typing import List
2
3class Solution:
4    def findMaximums(self, nums: List[int]) -> List[int]:
5        n = len(nums)
6        # Initialize the left boundary for each element's minimum window
7        left_boundaries = [-1] * n
8        # Initialize the right boundary for each element's minimum window
9        right_boundaries = [n] * n
10        stack = []
11
12        # Determine the previous less element for each number in nums
13        for index, value in enumerate(nums):
14            # Pop elements from the stack if the current value is less or equal
15            while stack and nums[stack[-1]] >= value:
16                stack.pop()
17            # Set the left boundary if there is a previous less element
18            if stack:
19                left_boundaries[index] = stack[-1]
20            stack.append(index)
21
22        # Reset the stack for determining next less element
23        stack = []
24
25        # Determine the next less element for each number in nums
26        for index in range(n - 1, -1, -1):
27            # Pop elements from the stack if the current number is less or equal
28            while stack and nums[stack[-1]] >= nums[index]:
29                stack.pop()
30            # Set the right boundary if there is a next less element
31            if stack:
32                right_boundaries[index] = stack[-1]
33            stack.append(index)
34
35        # Initialize the result array to store the maximums for each window size
36        results = [0] * n
37        # Update results array with the maximum values for each window size
38        for index in range(n):
39            window_size = right_boundaries[index] - left_boundaries[index] - 1
40            results[window_size - 1] = max(results[window_size - 1], nums[index])
41
42        # Propagate the maximums for larger window sizes
43        for index in range(n - 2, -1, -1):
44            results[index] = max(results[index], results[index + 1])
45
46        return results
47``````

## Java Solution

``````1import java.util.ArrayDeque;
2import java.util.Arrays;
3import java.util.Deque;
4
5public class Solution {
6    public int[] findMaximums(int[] nums) {
7        int n = nums.length;
8        // Initialize arrays to keep track of the left and right boundaries
9        int[] leftBoundaries = new int[n];
10        int[] rightBoundaries = new int[n];
11        // Fill the arrays with initial values indicating no boundary found yet
12        Arrays.fill(leftBoundaries, -1);
13        Arrays.fill(rightBoundaries, n);
14
15        // Stack to keep track of indices for which we haven't found a smaller number yet
16        Deque<Integer> stack = new ArrayDeque<>();
17
18        // Iterating from left to right to compute left boundaries
19        for (int i = 0; i < n; ++i) {
20            // Pop elements from the stack that are greater or equal to the current element
21            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
22                stack.pop();
23            }
24            // If stack is not empty, the current top is the closest left smaller element
25            if (!stack.isEmpty()) {
26                leftBoundaries[i] = stack.peek();
27            }
28            // Push the current index onto the stack
29            stack.push(i);
30        }
31        // Clear the stack for the next iteration
32        stack.clear();
33
34        // Iterating from right to left to compute right boundaries
35        for (int i = n - 1; i >= 0; --i) {
36            // Pop elements from the stack that are greater or equal to the current element
37            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
38                stack.pop();
39            }
40            // If stack is not empty, the current top is the closest right smaller element
41            if (!stack.isEmpty()) {
42                rightBoundaries[i] = stack.peek();
43            }
44            // Push the current index onto the stack
45            stack.push(i);
46        }
47
48        // Initialize the result array
49        int[] result = new int[n];
50        // Find the maximum value for every possible window size
51        for (int i = 0; i < n; ++i) {
52            int windowSize = rightBoundaries[i] - leftBoundaries[i] - 1;
53            result[windowSize - 1] = Math.max(result[windowSize - 1], nums[i]);
54        }
55        // Iterate to ensure each element represents the maximum for window size >= i+1
56        for (int i = n - 2; i >= 0; --i) {
57            result[i] = Math.max(result[i], result[i + 1]);
58        }
59        // Return the filled in result array
60        return result;
61    }
62}
63``````

## C++ Solution

``````1#include <vector>
2#include <stack>
3
4using std::vector;
5using std::stack;
6using std::max;
7
8class Solution {
9public:
10    // Function to find the maximums of subarrays of all possible sizes
11    vector<int> findMaximums(vector<int>& nums) {
12        int n = nums.size();
13
14        // Vectors to store indices of previous and next smaller elements
15        vector<int> left(n, -1);
16        vector<int> right(n, n);
17
18        // Stack to keep track of indices as we search for smaller elements
19        stack<int> stk;
20
21        // Calculate the previous smaller element for each element in nums
22        for (int i = 0; i < n; ++i) {
23            // Pop elements from the stack until the current element is greater
24            while (!stk.empty() && nums[stk.top()] >= nums[i]) {
25                stk.pop();
26            }
27            // If the stack isn't empty, set the left bound
28            if (!stk.empty()) {
29                left[i] = stk.top();
30            }
31            // Push the current index onto the stack
32            stk.push(i);
33        }
34
35        // Clear the stack to reuse it for the next smaller elements on the right
36        stk = stack<int>();
37
38        // Calculate the next smaller element for each element in nums
39        for (int i = n - 1; i >= 0; --i) {
40            // Pop elements from the stack until the current element is greater
41            while (!stk.empty() && nums[stk.top()] >= nums[i]) {
42                stk.pop();
43            }
44            // If the stack isn't empty, set the right bound
45            if (!stk.empty()) {
46                right[i] = stk.top();
47            }
48            // Push the current index onto the stack
49            stk.push(i);
50        }
51
52        // Vector to store the maximums of subarrays of all possible sizes
53        vector<int> maxSubarraySizes(n);
54
55        // Find the maximum element seen for each subarray size
56        for (int i = 0; i < n; ++i) {
57            // Calculate the size of the largest window that the current element can be the minimum
58            int windowSize = right[i] - left[i] - 1;
59            // Update the maximum value for this window size if the current element is larger
60            maxSubarraySizes[windowSize - 1] = max(maxSubarraySizes[windowSize - 1], nums[i]);
61        }
62
63        // Ensure the maximum value for each size is at least as large as for the size above
64        for (int i = n - 2; i >= 0; --i) {
65            maxSubarraySizes[i] = max(maxSubarraySizes[i], maxSubarraySizes[i + 1]);
66        }
67
68        // Return the vector of maximums
69        return maxSubarraySizes;
70    }
71};
72``````

## Typescript Solution

``````1// Import relevant tools from TypeScript's standard library
2import { Stack } from 'typescript-collections';
3
4// Method to find the maximums of subarrays of all possible sizes
5function findMaximums(nums: number[]): number[] {
6    const n: number = nums.length;
7
8    // Arrays to store indices of previous and next smaller elements
9    const left: number[] = new Array(n).fill(-1);
10    const right: number[] = new Array(n).fill(n);
11
12    // Stack to keep track of indices when searching for smaller elements
13    let stk: Stack<number> = new Stack<number>();
14
15    // Calculate the previous smaller element for each element in nums
16    for (let i = 0; i < n; ++i) {
17        // Pop elements from the stack until the current element is greater
18        while (!stk.isEmpty() && nums[stk.peek()!] >= nums[i]) {
19            stk.pop();
20        }
21        // If the stack isn't empty, set the left bound
22        if (!stk.isEmpty()) {
23            left[i] = stk.peek()!;
24        }
25        // Push the current index onto the stack
26        stk.push(i);
27    }
28
29    // Reset the stack to use for the next smaller elements on the right
30    stk = new Stack<number>();
31
32    // Calculate the next smaller element for each element in nums
33    for (let i = n - 1; i >= 0; --i) {
34        // Pop elements from the stack until the current element is greater
35        while (!stk.isEmpty() && nums[stk.peek()!] >= nums[i]) {
36            stk.pop();
37        }
38        // If the stack isn't empty, set the right bound
39        if (!stk.isEmpty()) {
40            right[i] = stk.peek()!;
41        }
42        // Push the current index onto the stack
43        stk.push(i);
44    }
45
46    // Initialize array to store the maximum values for subarrays of all sizes
47    const maxSubarraySizes: number[] = new Array(n).fill(0);
48
49    // Find the maximum element for each subarray size
50    for (let i = 0; i < n; ++i) {
51        // Calculate the size of the largest window where the current element is the smallest
52        const windowSize: number = right[i] - left[i] - 1;
53        // Update the maximum value for this window size if the current element is larger
54        maxSubarraySizes[windowSize - 1] = Math.max(maxSubarraySizes[windowSize - 1], nums[i]);
55    }
56
57    // Ensure the maximum value for each size is at least as large as for the size above
58    for (let i = n - 2; i >= 0; --i) {
59        maxSubarraySizes[i] = Math.max(maxSubarraySizes[i], maxSubarraySizes[i + 1]);
60    }
61
62    // Return the vector of maximums
63    return maxSubarraySizes;
64}
65
66// Here we would export the function if it's to be used in other modules
67export { findMaximums };
68``````

## Time and Space Complexity

The given Python code defines a method `findMaximums` which calculates the maximum elements for all subarray sizes in a non-decreasing order. Let's analyze its time and space complexity.

### Time Complexity

1. The initialization of the `left` and `right` lists with lengths of `n` has a time complexity of `O(n)` each.
2. The first loop to populate `left` array iterates over all elements and, in the worst case, each element is both pushed and popped from the stack exactly once, resulting in an `O(n)` complexity.
3. Similarly, the second loop for the `right` array also has an `O(n)` complexity, following the same reasoning.
4. The third loop to calculate the maximum for each subarray size also iterates over all `n` elements with constant-time operations inside the loop, so its complexity is `O(n)`.
5. The fourth loop, which is used for updating the `ans` array in the reverse direction also iterates `n` times with constant-time operations inside the loop, giving it `O(n)` complexity.

Since all loops execute sequentially and each has a complexity of `O(n)`, the total time complexity of the algorithm is `O(n) + O(n) + O(n) + O(n) + O(n) = O(5n)`, which simplifies to `O(n)`.

### Space Complexity

1. Extra space is used for the `left` and `right` arrays, and the stack (`stk`), each of size `n`, resulting in `3n` space.
2. The answer array `ans` also uses `n` space.

Therefore, the total extra space used by the algorithm is `4n`. Hence, the space complexity is `O(4n)`, which simplifies to `O(n)`.

In conclusion, the time complexity is `O(n)` and the space complexity is `O(n)`.

๐
Become an
Algo Monster

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ
โTA ๐จโ๐ซ