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:

Look at every subarray in nums that is exactly i+1 elements long.
In each subarray, identify the smallest element.
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.

Learn more about Stack and Monotonic Stack patterns.

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:

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.
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.
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.
After constructing left and right arrays, initialize the answer array ans with zeros, with the same size as nums.
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].
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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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.

Initialize arrays and stack:
- left = [-1, -1, -1, -1]
- right = [4, 4, 4, 4] (since n = 4)
- stk = [] (empty stack)
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.
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.
Initialize the answer array:
- ans = [0, 0, 0, 0]
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]
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.

Solution Implementation

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

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

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

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

The initialization of the left and right lists with lengths of n has a time complexity of O(n) each.
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.
Similarly, the second loop for the right array also has an O(n) complexity, following the same reasoning.
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).
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

Extra space is used for the left and right arrays, and the stack (stk), each of size n, resulting in 3n space.
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).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don’t know