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 exactlyi+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 thannums[i]
.right[i]
contains the index of the next smaller element thannums[i]
. If there is no such element, the default values are-1
forleft[i]
andn
forright[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
andright
with lengths equal to that ofnums
. Set all values inleft
to-1
and inright
ton
, wheren
is the size ofnums
. Also, create an empty liststk
to be used as our Monotonic Stack. -
Iterate through
nums
from left to right (using indexi
):- Pop elements from the stack
stk
while the top of the stack is greater than or equal to the current elementnums[i]
. - If
stk
is not empty after popping elements, it meansstk[-1]
is the previous smaller element's index, which we assign toleft[i]
. - Push the current index
i
ontostk
, indicating that we are consideringnums[i]
for the next elements' previous smaller check.
- Pop elements from the stack
-
Reset the stack
stk
and perform a similar process from right to left (using a decreasing indexi
):- 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 ofstk
is the next smaller element's index, which we assign toright[i]
. - Push the current index
i
ontostk
.
- Pop elements while the top of the stack is greater than or equal to
-
After constructing
left
andright
arrays, initialize the answer arrayans
with zeros, with the same size asnums
. -
For every index
i
innums
, calculate the widthm
as the number of subarrays wherenums[i]
is the minimum byright[i] - left[i] - 1
, and updateans[m - 1]
with the maximum of its current value andnums[i]
. -
Iterate through
ans
in reverse (starting from second to last element), making sure eachans[i]
is at least as large asans[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 EvaluatorExample 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]
(sincen = 4
)stk = []
(empty stack)
-
Left smaller elements: Iterate from left to right.
- For
i = 0
: Stack is empty, so leaveleft[0] = -1
. Push0
tostk
. - For
i = 1
: Pop0
becausenums[0] >= nums[1]
. Stack becomes empty, so leaveleft[1] = -1
. Push1
tostk
. - For
i = 2
: Stack's top element1
is not greater thannums[2]
, so leaveleft[2] = 1
. Push2
tostk
. - For
i = 3
: Stack's top element2
is not greater thannums[3]
, so leaveleft[3] = 2
. Push3
tostk
.
At the end of this step:
left = [-1, -1, 1, 2]
- Stack
stk
is reset to empty.
- For
-
Right smaller elements: Iterate from right to left.
- For
i = 3
: Stack is empty, so leaveright[3] = 4
. Push3
tostk
. - For
i = 2
: Stack's top element3
is greater thannums[2]
, soright[2] = 3
. Push2
tostk
. - For
i = 1
: Keep popping untilstk
is empty becausenums[3]
andnums[2]
are greater. Nowright[1] = 4
. Push1
tostk
. - For
i = 0
:stk
top is1
, andnums[1]
is greater thannums[0]
, soright[0] = 1
. Push0
tostk
.
At the end of this step:
right = [1, 4, 3, 4]
- Now we have both
left
andright
filled out.
- For
-
Initialize the answer array:
ans = [0, 0, 0, 0]
-
Calculate and update
ans
:- For
i = 0
: Widthm = right[0] - left[0] - 1 = 1
. Updateans[0]
tomax(ans[0], nums[0]) = 3
. - For
i = 1
: Widthm = right[1] - left[1] - 1 = 3
. Updateans[2]
tomax(ans[2], nums[1]) = 1
. - For
i = 2
: Widthm = right[2] - left[2] - 1 = 1
. Updateans[0]
tomax(ans[0], nums[2]) = 3
(no change). - For
i = 3
: Widthm = right[3] - left[3] - 1 = 1
. Updateans[0]
tomax(ans[0], nums[3]) = 4
.
After this:
ans = [4, 0, 1, 0]
- For
-
Adjust
ans
in reverse:- Iterate from
ans[2]
toans[0]
: Setans[i]
tomax(ans[i], ans[i + 1])
. - After adjustment:
ans = [4, 2, 1, 0]
(Fill in the non-updated spots with the next greater values)
- Iterate from
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
andright
lists with lengths ofn
has a time complexity ofO(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 anO(n)
complexity. - Similarly, the second loop for the
right
array also has anO(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 isO(n)
. - The fourth loop, which is used for updating the
ans
array in the reverse direction also iteratesn
times with constant-time operations inside the loop, giving itO(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
andright
arrays, and the stack (stk
), each of sizen
, resulting in3n
space. - The answer array
ans
also usesn
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.
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Monotonic Stack Deque Intro If you'd prefer a video div class responsive iframe iframe src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div The word monotonic means a list or
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!