Maximum of Minimum Values in All Subarrays

Maximum of Minimum Values in All Subarrays

What is this problem about?

The Maximum of Minimum Values in All Subarrays coding problem gives you an array nums. You need to find the maximum value among the minimums of all possible subarrays of nums. In other words, for every possible subarray nums[i...j], find its minimum element. Then, find the maximum among all these minimums.

Why is this asked in interviews?

Amazon uses this problem to test a candidate's understanding of arrays, stacks, and efficient computation of range minimum queries. A naive brute-force approach (O(N^3) or O(N^2)) is too slow. The optimal solution typically involves a monotonic stack to find the "next smaller element" and "previous smaller element" efficiently.

Algorithmic pattern used

Monotonic Stack: This problem is a classic application of a monotonic stack. For each element nums[i], we need to find the largest possible subarray (left_bound, right_bound) where nums[i] is the minimum element. Once we have these bounds for each nums[i], we know that nums[i] is a potential minimum for any subarray whose minimum is nums[i] and whose length is L = right_bound - left_bound - 1.

Algorithm:

1. Find Next Smaller Element (NSE): For each element nums[i], find the index of the first element to its right that is strictly smaller than nums[i]. If no such element exists, store N (array length). This can be done in O(N) using a monotonic increasing stack.

   • Example: nums = [10, 20, 30, 50, 10, 70, 30]. NSE = [4, 4, 4, 4, 7, 7, 7]

2. Find Previous Smaller Element (PSE): For each element nums[i], find the index of the first element to its left that is strictly smaller than nums[i]. If no such element exists, store -1. This can also be done in O(N) using a monotonic increasing stack (or by reversing the array and applying NSE logic).

   • Example: nums = [10, 20, 30, 50, 10, 70, 30]. PSE = [-1, 0, 1, 2, -1, 4, 4]

3. Compute Potential Answers for Each Length:

   • Create an array ans[L] of size N+1, initialized to -infinity. ans[L] will store the maximum of minimums for subarrays of length at least L.
   • For each i from 0 to N-1:
     • The length of the maximal subarray where nums[i] is the minimum is L = NSE[i] - PSE[i] - 1.
     • ans[L] = max(ans[L], nums[i]). This sets nums[i] as a candidate for the maximum of minimums for subarrays of exactly length L.

4. Propagate Maximums Downwards: This is the crucial step. If X is the minimum of a subarray of length L, then it is also the minimum of all subarrays of length L' < L that are contained within that maximal subarray. Therefore, the maximum of minimums for subarrays of length L' must be at least ans[L'] or ans[L'+1].

   • Iterate L from N-1 down to 1: ans[L] = max(ans[L], ans[L+1]).
   • The final answer for length L is ans[L].

Time Complexity: O(N) for NSE, PSE, and building ans array, and O(N) for propagation. Total O(N).

Example explanation

nums = [10, 20, 30, 50, 10, 70, 30] (N=7) PSE: [-1, 0, 1, 2, -1, 4, 4] NSE: [4, 4, 4, 4, 7, 7, 7]

Initialize ans array of size N+1 (8 elements) with -infinity.

Populate ans array based on maximal subarray lengths:

• i=0, nums[0]=10: L = NSE[0] - PSE[0] - 1 = 4 - (-1) - 1 = 4. ans[4] = max(-inf, 10) = 10.
• i=1, nums[1]=20: L = NSE[1] - PSE[1] - 1 = 4 - 0 - 1 = 3. ans[3] = max(-inf, 20) = 20.
• i=2, nums[2]=30: L = NSE[2] - PSE[2] - 1 = 4 - 1 - 1 = 2. ans[2] = max(-inf, 30) = 30.
• i=3, nums[3]=50: L = NSE[3] - PSE[3] - 1 = 4 - 2 - 1 = 1. ans[1] = max(-inf, 50) = 50.
• i=4, nums[4]=10: L = NSE[4] - PSE[4] - 1 = 7 - (-1) - 1 = 7. ans[7] = max(-inf, 10) = 10.
• i=5, nums[5]=70: L = NSE[5] - PSE[5] - 1 = 7 - 4 - 1 = 2. ans[2] = max(30, 70) = 70.
• i=6, nums[6]=30: L = NSE[6] - PSE[6] - 1 = 7 - 4 - 1 = 2. ans[2] remains 70.

ans array after step 3 (using 1-based indexing for length): ans = [?, 50, 70, 20, 10, -inf, -inf, 10]

Propagate maximums downwards (step 4):

• L=6: ans[6] = max(ans[6], ans[7]) = max(-inf, 10) = 10.
• L=5: ans[5] = max(ans[5], ans[6]) = max(-inf, 10) = 10.
• L=4: ans[4] = max(ans[4], ans[5]) = max(10, 10) = 10.
• L=3: ans[3] = max(ans[3], ans[4]) = max(20, 10) = 20.
• L=2: ans[2] = max(ans[2], ans[3]) = max(70, 20) = 70.
• L=1: ans[1] = max(ans[1], ans[2]) = max(50, 70) = 70.

Final ans array (excluding ans[0]): ans[1]=70, ans[2]=70, ans[3]=20, ans[4]=10, ans[5]=10, ans[6]=10, ans[7]=10. These are the maximum of minimums for subarrays of length 1, 2, ..., N.

Common mistakes candidates make

• Brute-force approach: O(N^2) or O(N^3) is too slow.
• Incorrectly finding NSE/PSE: Errors in stack logic for next/previous smaller elements.
• Missing the propagation step: The ans[L] = max(ans[L], ans[L+1]) step is crucial for correctly reflecting that an element that is the minimum for a longer subarray is also the minimum for all its shorter subarrays.

Interview preparation tip

For the Array Monotonic Stack Stack interview pattern, this problem is a cornerstone. Master the monotonic stack technique to efficiently find NSE/PSE. Recognize that this pattern is useful for problems involving range minimum/maximum queries on subarrays.