Maximum of Minimum Values in All Subarrays

Maximum of Minimum Values in All Subarrays - Problem

You are given an integer array nums of size n. You need to solve n queries for each integer i in the range 0 ≤ i < n.

To solve the ith query:

Find the minimum value in each possible subarray of size i + 1 of the array nums
Find the maximum of those minimum values

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [7,9,8,6,2]

› Output: [9,8,7,6,2]

💡 Note: Size 1: min values are [7,9,8,6,2], max = 9. Size 2: min values are [7,8,6,2], max = 8. Size 3: min values are [7,6,2], max = 7. Size 4: min values are [6,2], max = 6. Size 5: min value is [2], max = 2.

Example 2 — All Same Values

$ Input: nums = [5,5,5,5]

› Output: [5,5,5,5]

💡 Note: All elements are the same, so minimum of any subarray is 5, and maximum of minimums is always 5.

Example 3 — Decreasing Order

$ Input: nums = [10,6,3,1]

› Output: [10,6,3,1]

💡 Note: Size 1: max min = 10. Size 2: subarrays [10,6],[6,3],[3,1] have mins [6,3,1], max = 6. Size 3: subarrays [10,6,3],[6,3,1] have mins [3,1], max = 3. Size 4: subarray [10,6,3,1] has min = 1.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [7,9,8,6,2] with 5 elements

Process

For each size, find minimums of all subarrays, then take maximum

Output

Array [9,8,7,6,2] representing max of mins for each size

Key Takeaway

🎯 Key Insight: Each element dominates as minimum within a specific range of subarray sizes

Asked in

G Google 25 a Amazon 18 f Facebook 15 M Microsoft 12

The key insight is that each element dominates as minimum within a specific range, and we can use a monotonic stack to find these ranges efficiently. Best approach uses monotonic stack with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window with Deque	O(n²)	O(n)	Use sliding window with deque to efficiently find minimums in all subarrays of each size
Monotonic Stack Optimization	O(n)	O(n)	Use monotonic stack to find the range where each element is minimum, then compute answer efficiently
Brute Force - Check All Subarrays	O(n³)	O(1)	For each query size, generate all subarrays and find minimum of each, then take maximum

Sliding Window with Deque — Algorithm Steps

For each size i from 1 to n
Use sliding window of size i
Maintain deque of indices in increasing order of values
Front of deque gives minimum for current window

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set up window of target size

Slide

Move window and maintain minimum

Track

Keep maximum of all minimums

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int* solution(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* result = (int*)malloc(numsSize * sizeof(int));
    
    for (int size = 1; size <= numsSize; size++) {
        int maxOfMins = INT_MIN;
        int dq[1000];
        int front = 0, back = 0;
        
        // Process first window
        for (int i = 0; i < size; i++) {
            while (back > front && nums[dq[back-1]] >= nums[i]) {
                back--;
            }
            dq[back++] = i;
        }
        
        if (nums[dq[front]] > maxOfMins) {
            maxOfMins = nums[dq[front]];
        }
        
        // Process remaining windows
        for (int i = size; i < numsSize; i++) {
            // Remove elements outside window
            while (front < back && dq[front] <= i - size) {
                front++;
            }
            
            // Remove elements greater than current
            while (back > front && nums[dq[back-1]] >= nums[i]) {
                back--;
            }
            
            dq[back++] = i;
            if (nums[dq[front]] > maxOfMins) {
                maxOfMins = nums[dq[front]];
            }
        }
        
        result[size - 1] = maxOfMins;
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int nums[1000];
    int count = 0;
    char* ptr = line + 1;
    char* token = strtok(ptr, ",]");
    
    while (token != NULL) {
        nums[count++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, count, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n sizes, we slide window across n positions with O(1) deque operations

⚠ Quadratic Growth

Space Complexity

O(n)

Deque stores at most n indices

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window with Deque — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler