Problem Description

You have an integer array nums of size n. You need to answer n different queries, where each query i (for 0 <= i < n) asks you to:

1. Look at all possible subarrays of size i + 1 in the array
2. Find the minimum value in each of these subarrays
3. Return the maximum among all these minimum values

The final answer should be an array ans of size n, where ans[i] contains the answer to the i-th query.

For example, if nums = [1, 3, 2, 4]:

• Query 0 (subarray size 1): All subarrays are [1], [3], [2], [4]. Their minimums are 1, 3, 2, 4. The maximum of these is 4.
• Query 1 (subarray size 2): All subarrays are [1,3], [3,2], [2,4]. Their minimums are 1, 2, 2. The maximum of these is 2.
• Query 2 (subarray size 3): All subarrays are [1,3,2], [3,2,4]. Their minimums are 1, 2. The maximum of these is 2.
• Query 3 (subarray size 4): Only one subarray [1,3,2,4]. Its minimum is 1. The maximum is 1.

So the answer would be [4, 2, 2, 1].

The solution uses a monotonic stack approach to efficiently find, for each element, the largest subarray where that element is the minimum. The left[i] and right[i] arrays store the boundaries of the largest window where nums[i] is the minimum element. The distance right[i] - left[i] - 1 gives the maximum window size where nums[i] can be the minimum, which helps determine which query answers should consider this element.

Intuition

The key insight is to reverse the problem's perspective. Instead of finding minimums for each subarray size, we can think about: for each element in the array, what's the largest subarray where this element is the minimum?

Consider any element nums[i]. If we know the largest subarray where nums[i] is the minimum element, we can determine which query answers this element contributes to. For instance, if nums[i] is the minimum in a subarray of maximum length m, then it could potentially be the answer for query m-1 (subarrays of size m).

To find the largest subarray where each element is the minimum, we need to find:

• The nearest smaller element to the left (or -1 if none exists)
• The nearest smaller element to the right (or n if none exists)

The region between these boundaries is where nums[i] can be the minimum. We use monotonic stacks for this - maintaining an increasing stack helps us efficiently find these boundaries in O(n) time.

Once we know that nums[i] can be the minimum for subarrays up to size m, we update ans[m-1] = max(ans[m-1], nums[i]). This is because for query m-1 (subarrays of size m), nums[i] is one possible minimum value we need to consider.

The final trick is recognizing that if an element is the answer for subarrays of size k, it's also a valid candidate for all smaller subarray sizes. So we propagate the maximum values backwards: ans[i] = max(ans[i], ans[i+1]). This ensures that each query gets the best possible answer from all applicable elements.

Learn more about Stack and Monotonic Stack patterns.

Solution Approach

The implementation uses monotonic stacks to find the boundaries for each element where it serves as the minimum value.

Step 1: Find Left Boundaries We iterate through the array from left to right with a stack. For each element nums[i]:

• Pop elements from the stack while nums[stk[-1]] >= nums[i] (remove elements that are greater than or equal to current)
• The top of the stack (if exists) gives us left[i] - the index of the nearest smaller element to the left
• Push current index i onto the stack

This maintains a strictly increasing stack, ensuring we always find the nearest smaller element.

Step 2: Find Right Boundaries Similar process but iterating from right to left:

• For each position i, pop elements while nums[stk[-1]] >= nums[i]
• The top of the stack (if exists) gives us right[i] - the index of the nearest smaller element to the right
• Push current index i onto the stack

Step 3: Calculate Maximum Window Sizes For each element at position i:

• Calculate m = right[i] - left[i] - 1, which is the maximum subarray length where nums[i] is the minimum
• Update ans[m-1] = max(ans[m-1], nums[i]) because nums[i] could be the answer for query m-1 (subarrays of size m)

Step 4: Propagate Maximum Values Since larger elements can also be candidates for smaller subarray sizes, we propagate backwards:

for i in range(n - 2, -1, -1):
    ans[i] = max(ans[i], ans[i + 1])

This ensures that if an element is the best answer for size k, it's also considered for all sizes less than k.

Time Complexity: O(n) - each element is pushed and popped from the stack at most once Space Complexity: O(n) - for the left, right, and stack arrays

Example Walkthrough

Let's walk through the solution with nums = [3, 1, 5, 4].

Step 1: Find Left Boundaries

• i=0, nums[0]=3: Stack is empty. left[0] = -1. Stack: [0]
• i=1, nums[1]=1: Pop 0 (3≥1). Stack empty. left[1] = -1. Stack: [1]
• i=2, nums[2]=5: nums[1]=1 < 5. left[2] = 1. Stack: [1, 2]
• i=3, nums[3]=4: Pop 2 (5≥4). nums[1]=1 < 4. left[3] = 1. Stack: [1, 3]

Result: left = [-1, -1, 1, 1]

Step 2: Find Right Boundaries

• i=3, nums[3]=4: Stack is empty. right[3] = 4. Stack: [3]
• i=2, nums[2]=5: nums[3]=4 < 5. right[2] = 3. Stack: [3, 2]
• i=1, nums[1]=1: Pop 2 (5≥1), pop 3 (4≥1). Stack empty. right[1] = 4. Stack: [1]
• i=0, nums[0]=3: nums[1]=1 < 3. right[0] = 1. Stack: [1, 0]

Result: right = [1, 4, 3, 4]

Step 3: Calculate Maximum Window Sizes and Update ans Initialize: ans = [0, 0, 0, 0]

• i=0, nums[0]=3: window size = 1 - (-1) - 1 = 1 Update ans[0] = max(0, 3) = 3
• i=1, nums[1]=1: window size = 4 - (-1) - 1 = 4 Update ans[3] = max(0, 1) = 1
• i=2, nums[2]=5: window size = 3 - 1 - 1 = 1 Update ans[0] = max(3, 5) = 5
• i=3, nums[3]=4: window size = 4 - 1 - 1 = 2 Update ans[1] = max(0, 4) = 4

After Step 3: ans = [5, 4, 0, 1]

Step 4: Propagate Maximum Values Backwards

• i=2: ans[2] = max(0, 1) = 1
• i=1: ans[1] = max(4, 1) = 4
• i=0: ans[0] = max(5, 4) = 5

Final Result: ans = [5, 4, 1, 1]

Verification:

• Query 0 (size 1): Subarrays [3], [1], [5], [4] → mins: 3, 1, 5, 4 → max = 5 ✓
• Query 1 (size 2): Subarrays [3,1], [1,5], [5,4] → mins: 1, 1, 4 → max = 4 ✓
• Query 2 (size 3): Subarrays [3,1,5], [1,5,4] → mins: 1, 1 → max = 1 ✓
• Query 3 (size 4): Subarray [3,1,5,4] → min: 1 → max = 1 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of several linear passes through the array:

• First loop to calculate left array: Each element is pushed and popped from the stack at most once, resulting in O(n) operations
• Second loop to calculate right array: Similarly, each element is pushed and popped at most once, giving O(n) operations
• Third loop to populate initial ans array: Iterates through all n elements once, taking O(n) time
• Fourth loop to propagate maximum values backward: Iterates through n-1 elements once, taking O(n) time

Total time complexity: O(n) + O(n) + O(n) + O(n) = O(n)

Space Complexity: O(n)

The algorithm uses the following additional space:

• left array of size n: O(n) space
• right array of size n: O(n) space
• stk stack which can contain at most n elements: O(n) space
• ans array of size n: O(n) space (this is the output array, often not counted in auxiliary space)

If we count only auxiliary space (excluding the output): O(n) If we include the output array: O(n)

Total space complexity: O(n)

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

Common Pitfalls

1. Incorrect Handling of Equal Elements

The most critical pitfall in this solution is how we handle equal elements when building the monotonic stack. The condition nums[stack[-1]] >= num (using >= instead of >) is essential for correctness.

Why this matters: When multiple equal elements exist, we need to ensure each element considers the correct window boundaries. Using >= ensures that when we have duplicate values, each instance gets its proper left boundary.

Example of the bug:

# INCORRECT: Using only > instead of >=
while stack and nums[stack[-1]] > num:  # Bug!
    stack.pop()

Consider nums = [2, 2, 2]:

• With >: Each 2 would consider all other 2s as part of its window, leading to incorrect window sizes
• With >=: Each 2 gets properly bounded, ensuring correct window size calculations

2. Forgetting the Propagation Step

Another common mistake is omitting the backward propagation step:

# This step is ESSENTIAL - don't forget it!
for i in range(n - 2, -1, -1):
    result[i] = max(result[i], result[i + 1])

Why this matters: Not all window sizes might have a direct element that serves as the minimum for exactly that size. The propagation ensures that if an element can be the answer for a larger window, it's also considered for smaller windows.

Example scenario: If nums = [5, 3, 1, 4], element 3 might be the best answer for windows of size 2, but there might not be any element that's the minimum for exactly size 1 subarrays. The propagation ensures the answer for size 1 considers element 3 as well.

3. Off-by-One Errors in Window Size Calculation

The window size calculation and array indexing can be confusing:

window_size = right_boundaries[i] - left_boundaries[i] - 1
result[window_size - 1] = max(result[window_size - 1], nums[i])

Common mistakes:

• Forgetting the -1 when calculating window size
• Forgetting the -1 when indexing into the result array (window size k corresponds to index k-1)
• Using window_size directly as the index instead of window_size - 1

4. Stack Initialization Between Left and Right Passes

Forgetting to reset the stack between computing left and right boundaries:

# After computing left boundaries
stack = []  # Don't forget to reset!
# Before computing right boundaries

Using the same stack without clearing it would produce completely incorrect boundaries for the right side.

Solution to Avoid These Pitfalls:

1. Always use >= in the while condition for both left and right boundary calculations
2. Include comprehensive test cases with duplicate elements to verify correct handling
3. Add the propagation step and test with arrays where not all window sizes have direct minimum elements
4. Use descriptive variable names like window_size instead of just m to make the logic clearer
5. Add assertions or checks during development to verify boundaries make sense (e.g., left[i] < i < right[i])