We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum of Minimum Values in All Subarrays

Number: 2072

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given an integer array nums of size n, for each subarray size (i + 1) where 0 <= i < n, compute the minimum value in every contiguous subarray of that size. Then, among those minimum values, determine the maximum value. Return an array ans of size n such that ans[i] is the answer for the subarrays of size (i + 1).

Key Insights

  • For each element, determine the window in which it is the minimum.
  • Use monotonic stacks to compute the previous and next smaller element indices efficiently.
  • Each element's contribution can be mapped to a specific subarray size where it acts as the subarray minimum.
  • Combine these contributions to build the final answer, then propagate the maximum values for shorter window sizes.

Space and Time Complexity

Time Complexity: O(n) – Each element is pushed and popped from the stack at most once. Space Complexity: O(n) – For the stack and result array.

Solution

To solve the problem, we first compute for each element in nums the farthest distance to the left (previous less element) and to the right (next less element) where the current element is still the minimum. These distances determine the size of the largest subarray in which the element is the minimum.

The steps are as follows:

  1. Create two arrays, left and right, to store the previous less and next less distance for each element.
  2. Use a monotonic stack to fill the left array. For each element, pop from the stack until an element smaller than the current element is found.
  3. Similarly, use a monotonic stack (traversing from right to left) to fill the right array.
  4. Compute the length of the window for which each element is the minimum as: windowLength = left[i] + right[i] - 1.
  5. For each computed window size, update an ans array with the maximum element that acts as the minimum for that window size.
  6. Finally, iterate backward over ans to ensure that for any smaller window size the answer is no smaller than for a larger window that can be achieved.

This algorithm leverages monotonic stacks and contributes each element in one pass, resulting in an optimal solution.

Code Solutions

# Python solution with detailed comments.
def maxOfMinValues(nums):
    n = len(nums)
    left = [0] * n  # stores count of elements to the left where nums[i] is minimum (including itself)
    right = [0] * n  # stores count of elements to the right where nums[i] is minimum (including itself)
    stack = []

    # Calculate previous less elements count for each element
    for i in range(n):
        # Pop until stack is empty or top element is less than current number
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        # If stack is empty, then no previous smaller; otherwise, calculate distance
        left[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)
    
    # Reset stack for counting next smaller elements
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        right[i] = n - i if not stack else stack[-1] - i
        stack.append(i)

    # Initialize answer array with -infinity values (or 0, since constraints have non-negative numbers)
    ans = [0] * n
    for i in range(n):
        # window length where nums[i] is minimum
        window_length = left[i] + right[i] - 1
        # Decrement index by 1 to match answer array index (window size i+1)
        ans[window_length - 1] = max(ans[window_length - 1], nums[i])
    
    # Some entries in ans might be zero or lower than a result from a larger window, so propagate backwards.
    for i in range(n - 2, -1, -1):
        ans[i] = max(ans[i], ans[i + 1])
    
    return ans

# Example usage:
print(maxOfMinValues([0,1,2,4]))  # Expected: [4,2,1,0]
← Back to All Questions