LeetCode 1950 - Maximum of Minimum Values in All Subarrays

This problem asks us to compute, for every possible subarray size, the best possible minimum value among all subarrays of that size. Given an array nums of length n, we must evaluate every window size from 1 to n. For each size k, we consider all contiguous subarrays of length k.

leetcodemediumarraystackmonotonic-stack

LeetCode Problem 1950

Difficulty: 🟡 Medium
Topics: Array, Stack, Monotonic Stack

Solution

Problem Understanding

This problem asks us to compute, for every possible subarray size, the best possible minimum value among all subarrays of that size.

Given an array nums of length n, we must evaluate every window size from 1 to n. For each size k, we consider all contiguous subarrays of length k. Every such subarray has a minimum element. Among all those minimum values, we select the maximum one.

The output array ans has length n, where:

  • ans[0] corresponds to subarrays of size 1
  • ans[1] corresponds to subarrays of size 2
  • ans[i] corresponds to subarrays of size i + 1

The key difficulty is that the constraints are large:

  • n can be up to 100000
  • A naive nested-window solution becomes too slow

A brute-force approach that explicitly computes all subarrays would require quadratic or cubic work, which is not feasible at this scale.

The important observation is that each element can act as the minimum for a range of subarrays. Instead of iterating over every subarray, we can determine the largest window size for which a particular element remains the minimum. This transforms the problem into a monotonic stack problem.

Several edge cases are important:

  • Arrays with all equal values
  • Strictly increasing arrays
  • Strictly decreasing arrays
  • Arrays containing duplicate minima
  • Arrays of size 1

Handling duplicates correctly is especially important because incorrect inequality choices in the monotonic stack can produce overlapping ranges or missed windows.

Approaches

Brute Force Approach

The most direct solution is to evaluate every possible subarray.

For every window size k:

  1. Enumerate all subarrays of length k
  2. Compute the minimum value in each subarray
  3. Track the maximum among those minimums

For example, with nums = [0,1,2,4] and k = 2:

  • [0,1] -> min = 0
  • [1,2] -> min = 1
  • [2,4] -> min = 2

The answer for size 2 is 2.

This method is correct because it explicitly checks every required subarray. However, it is far too slow.

If we compute minima naively, then:

  • There are O(n) window sizes
  • Each size has O(n) subarrays
  • Each minimum computation costs O(n)

Total complexity becomes O(n^3).

Even with sliding window optimizations, achieving all answers separately still leads to excessive work.

Optimal Approach

The optimal solution uses a monotonic stack.

The central insight is this:

Instead of asking:

"What is the minimum for every subarray?"

we ask:

"For which subarrays is a given element the minimum?"

For each element nums[i], we determine:

  • The nearest smaller element on the left
  • The nearest smaller element on the right

These boundaries tell us the largest window in which nums[i] remains the minimum value.

If:

  • left[i] is the index of the previous smaller element
  • right[i] is the index of the next smaller element

then nums[i] is the minimum for all windows inside:

(left[i], right[i])

The maximum window length is:

right[i] - left[i] - 1

This means:

  • nums[i] can serve as the minimum for a window of that size
  • Therefore it is a candidate answer for that window length

We compute these ranges in linear time using monotonic stacks.

After filling candidate answers, we propagate values backward because if a value works for a larger window, it also constrains smaller windows.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Explicitly checks all subarrays
Optimal O(n) O(n) Uses monotonic stacks to compute contribution ranges

Algorithm Walkthrough

Step 1: Compute previous smaller elements

We maintain an increasing monotonic stack.

For each index i:

  • Pop elements while the top of the stack is greater than or equal to nums[i]
  • The remaining top becomes the previous smaller element
  • If the stack is empty, use -1

This gives the left boundary where nums[i] stops being the minimum.

Step 2: Compute next smaller elements

We repeat the process from right to left.

For each index i:

  • Pop elements while the top is greater than or equal to nums[i]
  • The remaining top becomes the next smaller element
  • If none exists, use n

This gives the right boundary.

Step 3: Determine the maximum window size for each element

For every index i:

window_size = right[i] - left[i] - 1

This is the largest subarray length where nums[i] is the minimum.

We update:

ans[window_size - 1] = max(ans[window_size - 1], nums[i])

because we want the maximum possible minimum value for each window size.

Step 4: Fill missing entries

Some window sizes may remain unset.

Example:

[50, 0, 10, 0]

The answers must be non-increasing as window size grows.

If a value works for a larger window, it also constrains smaller windows.

So we process from right to left:

ans[i] = max(ans[i], ans[i + 1])

This fills all missing values correctly.

Why it works

For every element, the monotonic stack identifies the largest contiguous range where that element is the smallest value. Any subarray entirely inside that range has that element as its minimum.

Thus, every element contributes exactly to the window sizes where it can serve as the minimum. Taking the maximum contribution for each window size guarantees the correct answer.

The backward propagation step works because the answer sequence is monotonic:

ans[i] >= ans[i + 1]

Larger windows cannot have larger maximum minimums than smaller windows.

Python Solution

from typing import List

class Solution:
    def findMaximums(self, nums: List[int]) -> List[int]:
        n = len(nums)

        left = [-1] * n
        right = [n] * n

        stack = []

        # Previous smaller element
        for i in range(n):
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()

            if stack:
                left[i] = stack[-1]

            stack.append(i)

        stack.clear()

        # Next smaller element
        for i in range(n - 1, -1, -1):
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()

            if stack:
                right[i] = stack[-1]

            stack.append(i)

        ans = [0] * n

        # Assign values to window sizes
        for i in range(n):
            window_size = right[i] - left[i] - 1
            ans[window_size - 1] = max(
                ans[window_size - 1],
                nums[i]
            )

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

        return ans

The implementation begins by computing the nearest smaller elements on both sides of every position. The monotonic stack ensures that every element is pushed and popped at most once, giving linear complexity.

The left array stores the index of the previous smaller element. The right array stores the next smaller element.

Once those boundaries are known, the code computes the largest window where each element remains the minimum. That window size determines which answer slot the element contributes to.

Finally, the backward pass fills gaps and enforces the monotonic property of the answers.

Go Solution

func findMaximums(nums []int) []int {
	n := len(nums)

	left := make([]int, n)
	right := make([]int, n)

	for i := 0; i < n; i++ {
		left[i] = -1
		right[i] = n
	}

	stack := []int{}

	// Previous smaller element
	for i := 0; i < n; i++ {
		for len(stack) > 0 && nums[stack[len(stack)-1]] >= nums[i] {
			stack = stack[:len(stack)-1]
		}

		if len(stack) > 0 {
			left[i] = stack[len(stack)-1]
		}

		stack = append(stack, i)
	}

	stack = []int{}

	// Next smaller element
	for i := n - 1; i >= 0; i-- {
		for len(stack) > 0 && nums[stack[len(stack)-1]] >= nums[i] {
			stack = stack[:len(stack)-1]
		}

		if len(stack) > 0 {
			right[i] = stack[len(stack)-1]
		}

		stack = append(stack, i)
	}

	ans := make([]int, n)

	// Assign values to window sizes
	for i := 0; i < n; i++ {
		windowSize := right[i] - left[i] - 1

		if nums[i] > ans[windowSize-1] {
			ans[windowSize-1] = nums[i]
		}
	}

	// Fill missing values
	for i := n - 2; i >= 0; i-- {
		if ans[i+1] > ans[i] {
			ans[i] = ans[i+1]
		}
	}

	return ans
}

The Go implementation follows the same algorithmic structure as the Python version.

Slices are used for stacks because appending and truncating are efficient. Integer overflow is not an issue because values are bounded by 10^9, which safely fits inside Go's int on standard LeetCode environments.

The arrays are initialized with sentinel values:

  • -1 for missing left boundaries
  • n for missing right boundaries

This simplifies window length computation.

Worked Examples

Example 1

nums = [0,1,2,4]

Previous Smaller Array

Index Value Previous Smaller Index
0 0 -1
1 1 0
2 2 1
3 4 2

Next Smaller Array

Index Value Next Smaller Index
0 0 4
1 1 4
2 2 4
3 4 4

Window Contributions

Index Value Window Size Contribution
0 0 4 ans[3] = 0
1 1 3 ans[2] = 1
2 2 2 ans[1] = 2
3 4 1 ans[0] = 4

Final answer:

[4,2,1,0]

Example 2

nums = [10,20,50,10]

Previous Smaller Array

Index Value Previous Smaller Index
0 10 -1
1 20 0
2 50 1
3 10 -1

Next Smaller Array

Index Value Next Smaller Index
0 10 4
1 20 3
2 50 3
3 10 4

Window Contributions

Index Value Window Size Contribution
0 10 4 ans[3] = 10
1 20 2 ans[1] = 20
2 50 1 ans[0] = 50
3 10 4 ans[3] = 10

After propagation:

[50,20,10,10]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is pushed and popped from the stack at most once
Space O(n) Arrays and stacks store up to n elements

The algorithm is linear because monotonic stacks avoid repeated scanning. Every index participates in stack operations a constant number of times.

The auxiliary arrays left, right, and ans each require linear space.

Test Cases

from typing import List

class Solution:
    def findMaximums(self, nums: List[int]) -> List[int]:
        n = len(nums)

        left = [-1] * n
        right = [n] * n

        stack = []

        for i in range(n):
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()

            if stack:
                left[i] = stack[-1]

            stack.append(i)

        stack.clear()

        for i in range(n - 1, -1, -1):
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()

            if stack:
                right[i] = stack[-1]

            stack.append(i)

        ans = [0] * n

        for i in range(n):
            size = right[i] - left[i] - 1
            ans[size - 1] = max(ans[size - 1], nums[i])

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

        return ans

sol = Solution()

assert sol.findMaximums([0,1,2,4]) == [4,2,1,0]  # provided example
assert sol.findMaximums([10,20,50,10]) == [50,20,10,10]  # provided example

assert sol.findMaximums([5]) == [5]  # single element

assert sol.findMaximums([1,2,3,4,5]) == [5,4,3,2,1]  # strictly increasing

assert sol.findMaximums([5,4,3,2,1]) == [5,4,3,2,1]  # strictly decreasing

assert sol.findMaximums([2,2,2,2]) == [2,2,2,2]  # all duplicates

assert sol.findMaximums([1,3,2,4]) == [4,2,2,1]  # mixed ordering

assert sol.findMaximums([7,7,1,7,7]) == [7,7,1,1,1]  # repeated minimum

assert sol.findMaximums([9,8]) == [9,8]  # small decreasing

assert sol.findMaximums([1,1,1,2]) == [2,1,1,1]  # duplicate boundaries

Test Summary

Test Why
[0,1,2,4] Validates increasing sequence
[10,20,50,10] Validates mixed structure
[5] Smallest possible input
[1,2,3,4,5] Strictly increasing case
[5,4,3,2,1] Strictly decreasing case
[2,2,2,2] Duplicate handling
[1,3,2,4] Internal minimum transitions
[7,7,1,7,7] Global minimum dominates large windows
[9,8] Small edge case
[1,1,1,2] Equal values with distinct maximum

Edge Cases

One important edge case is an array containing all identical values, such as [2,2,2,2]. Duplicate handling is a common source of bugs in monotonic stack problems. If the stack comparisons use inconsistent inequalities, elements may incorrectly overlap ranges or leave gaps. This implementation consistently uses >= while popping, ensuring duplicates are handled correctly and every window receives the proper answer.

Another important case is a strictly increasing array like [1,2,3,4,5]. In this situation, every element becomes the minimum for all windows extending leftward. The algorithm correctly identifies progressively larger ranges, producing answers [5,4,3,2,1].

A strictly decreasing array such as [5,4,3,2,1] is also significant because every new element immediately becomes the smallest seen so far. This stresses the stack popping logic heavily. Since every index is still pushed and popped only once, the algorithm maintains linear complexity.

The smallest valid input, a single-element array like [5], must also work correctly. The element becomes the minimum for the only possible window of size 1, so the answer is simply [5]. The boundary initialization with -1 and n ensures this case works naturally without special handling.