Skip to main content
Talentd

Maximum of Minimum Values in All Subarrays - Solution & Explanation

MediumPremiumFree on FleetCodeArrayStackMonotonic Stack6 min readAsked at: Amazon
Practice this problem

Problem Statement

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:

  1. Find the minimum value in each possible subarray of size i + 1 of the array nums.
  2. Find the maximum of those minimum values. This maximum is the answer to the query.

Return a 0-indexed integer array ans of size n such that ans[i] is the answer to the ith query.

A subarray is a contiguous sequence of elements in an array.

 

Example 1:

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:

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 <= 105
  • 0 <= nums[i] <= 109

Approach Overview

Problem Overview: Given an integer array, compute the maximum among the minimum values of all subarrays for every possible window size from 1 to n. For example, among all subarrays of size k, find their minimum values and report the largest of those minimums. The result is an array of length n.

Approach 1: Brute Force Window Enumeration (O(n^3) time, O(1) space)

Enumerate every possible subarray size k. For each size, slide a window across the array and compute the minimum value inside that window. Track the maximum among those minimums. Computing the minimum for each window requires scanning up to k elements, which makes the total complexity cubic in the worst case. This approach is useful for understanding the problem definition but becomes impractical once the array grows beyond a few thousand elements.

Approach 2: Expand Each Minimum Using Monotonic Stack (O(n) time, O(n) space)

The key observation: instead of iterating over window sizes, determine the largest window where each element acts as the minimum. Use a monotonic stack to compute the previous smaller and next smaller element for every index. These boundaries define the span where arr[i] is the smallest value. If the distance between those boundaries is len, then arr[i] can serve as the minimum for a window of size len. Update result[len] with max(result[len], arr[i]). After processing all elements, propagate values backward so smaller windows inherit the best values from larger windows.

This approach converts a window enumeration problem into a boundary discovery problem. The stack maintains indices in increasing order of values while scanning the array. Each element is pushed and popped at most once, giving linear time complexity. The method relies heavily on patterns common in stack and array problems, particularly those involving nearest smaller elements.

Recommended for interviews: Interviewers expect the monotonic stack solution. A brute force explanation shows you understand the problem definition, but the optimal O(n) approach demonstrates familiarity with nearest-smaller-element patterns and span calculations, which frequently appear in advanced array and stack questions.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Window EnumerationO(n^3)O(1)Small arrays or when demonstrating the problem logic before optimizing
Monotonic Stack with Span CalculationO(n)O(n)General case and interview settings; handles large arrays efficiently

Video Solution

Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python • NeetCode • 605,141 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum of Minimum Values in All Subarrays easy or hard?
The problem is typically rated Medium because the brute force idea is straightforward but the optimal solution requires recognizing a monotonic stack pattern. Candidates who have practiced nearest smaller element problems usually identify the O(n) approach quickly.
Maximum of Minimum Values in All Subarrays Python/Java solution
Most implementations compute previous and next smaller indices using a stack, determine the window length for each element, and update a result array. The same logic translates directly across Python, Java, C++, and Go because it only relies on array iteration and stack operations.
How to solve Maximum of Minimum Values in All Subarrays in O(n)?
Compute previous smaller and next smaller indices using a monotonic increasing stack. These indices define the range where each element is the minimum. Calculate the window length where that element dominates and update the answer for that window size. Finally propagate results from larger windows to smaller ones so every window size has the correct maximum minimum value.
What is the best approach for Maximum of Minimum Values in All Subarrays?
The optimal solution uses a monotonic stack to find the previous smaller and next smaller element for every index. These boundaries determine the maximum window size where each element remains the minimum. Each element contributes to a specific window length, and the algorithm updates the maximum minimum value for that length. The approach runs in O(n) time with O(n) space.
Is Maximum of Minimum Values in All Subarrays asked at Google/Amazon/Meta?
Problems involving monotonic stacks and nearest smaller elements frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this question are common because they test stack patterns, array span calculations, and optimization from brute force to linear time.
What data structure is used in Maximum of Minimum Values in All Subarrays?
The core data structure is a monotonic stack that stores indices of the array in increasing order of values. It efficiently finds previous and next smaller elements. Arrays are also used to store span boundaries and the final result for each window size.
What is the time complexity of Maximum of Minimum Values in All Subarrays?
The optimal monotonic stack solution runs in O(n) time because each element is pushed and popped from the stack at most once. Additional linear passes are used to fill the result array. Space complexity is O(n) for the stack and result storage.

Ready to solve this problem?

Practice Maximum of Minimum Values in All Subarrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays