MediumStacks QueuesAI interview only
Maximum Of Minimum Values In All Subarrays
Asked atamazongooglemicrosoftbloomberg
01 · Problem
You are given an integer array nums of length n. For every window size k from 1 to n, look at every contiguous subarray of length k, take the minimum of each one, and then take the largest of those minimums.
Return an array ans of length n where ans[k - 1] is that value for window size k.
02 · Examples
Example 01
Input
nums = [0,1,2,4]
Output
[4,2,1,0]
Size 1: minimums are 0,1,2,4 -> max 4. Size 2: minimums 0,1,2 -> 2. Size 3: minimums 0,1 -> 1. Size 4: minimum 0 -> 0.
Example 02
Input
nums = [10,20,50,10]
Output
[50,20,10,10]
Size 1 -> 50. Size 2: windows give 10,20,10 -> 20. Size 3: windows give 10,10 -> 10. Size 4 -> 10.
Example 03
Input
nums = [5]
Output
[5]
Only one window of size 1, whose minimum is 5.
03 · Constraints
- 01n == nums.length
- 021 <= n <= 105
- 030 <= nums[i] <= 109
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.