LeetCode 1950. Maximum of Minimum Values in All Subarrays Solution in Java, C++, Python & Go | Explanation + Code

Description

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

To solve the ith query:

1. Find the minimum value in each possible subarray of size i + 1 of the array nums.
2. Find the maximum of those minimum values. This maximum is the answer to the query.

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.

 

Example 1:

Input: nums = [0,1,2,4]
Output: [4,2,1,0]
Explanation:
i=0:
- The subarrays of size 1 are [0], [1], [2], [4]. The minimum values are 0, 1, 2, 4.
- The maximum of the minimum values is 4.
i=1:
- The subarrays of size 2 are [0,1], [1,2], [2,4]. The minimum values are 0, 1, 2.
- The maximum of the minimum values is 2.
i=2:
- The subarrays of size 3 are [0,1,2], [1,2,4]. The minimum values are 0, 1.
- The maximum of the minimum values is 1.
i=3:
- There is one subarray of size 4, which is [0,1,2,4]. The minimum value is 0.
- There is only one value, so the maximum is 0.

Example 2:

Input: nums = [10,20,50,10]
Output: [50,20,10,10]
Explanation:
i=0:
- The subarrays of size 1 are [10], [20], [50], [10]. The minimum values are 10, 20, 50, 10.
- The maximum of the minimum values is 50.
i=1:
- The subarrays of size 2 are [10,20], [20,50], [50,10]. The minimum values are 10, 20, 10.
- The maximum of the minimum values is 20.
i=2:
- The subarrays of size 3 are [10,20,50], [20,50,10]. The minimum values are 10, 10.
- The maximum of the minimum values is 10.
i=3:
- There is one subarray of size 4, which is [10,20,50,10]. The minimum value is 10.
- There is only one value, so the maximum is 10.

 

Constraints:

• n == nums.length
• 1 <= n <= 105
• 0 <= nums[i] <= 109

Solutions

Solution 1

PythonJavaC++Go

class Solution: def findMaximums(self, nums: List[int]) -> List[int]: n = len(nums) left = [-1] * n right = [n] * n stk = [] for i, x in enumerate(nums): while stk and nums[stk[-1]] >= x: stk.pop() if stk: left[i] = stk[-1] stk.append(i) stk = [] for i in range(n - 1, -1, -1): while stk and nums[stk[-1]] >= nums[i]: stk.pop() if stk: right[i] = stk[-1] stk.append(i) ans = [0] * n for i in range(n): m = right[i] - left[i] - 1 ans[m - 1] = max(ans[m - 1], nums[i]) for i in range(n - 2, -1, -1): ans[i] = max(ans[i], ans[i + 1]) return ans(code-box)

class Solution { public int[] findMaximums(int[] nums) { int n = nums.length; int[] left = new int[n]; int[] right = new int[n]; Arrays.fill(left, -1); Arrays.fill(right, n); Deque<Integer> stk = new ArrayDeque<>(); for (int i = 0; i < n; ++i) { while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) { stk.pop(); } if (!stk.isEmpty()) { left[i] = stk.peek(); } stk.push(i); } stk.clear(); for (int i = n - 1; i >= 0; --i) { while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) { stk.pop(); } if (!stk.isEmpty()) { right[i] = stk.peek(); } stk.push(i); } int[] ans = new int[n]; for (int i = 0; i < n; ++i) { int m = right[i] - left[i] - 1; ans[m - 1] = Math.max(ans[m - 1], nums[i]); } for (int i = n - 2; i >= 0; --i) { ans[i] = Math.max(ans[i], ans[i + 1]); } return ans; } }(code-box)

class Solution { public: vector<int> findMaximums(vector<int>& nums) { int n = nums.size(); vector<int> left(n, -1); vector<int> right(n, n); stack<int> stk; for (int i = 0; i < n; ++i) { while (!stk.empty() && nums[stk.top()] >= nums[i]) { stk.pop(); } if (!stk.empty()) { left[i] = stk.top(); } stk.push(i); } stk = stack<int>(); for (int i = n - 1; i >= 0; --i) { while (!stk.empty() && nums[stk.top()] >= nums[i]) { stk.pop(); } if (!stk.empty()) { right[i] = stk.top(); } stk.push(i); } vector<int> ans(n); for (int i = 0; i < n; ++i) { int m = right[i] - left[i] - 1; ans[m - 1] = max(ans[m - 1], nums[i]); } for (int i = n - 2; i >= 0; --i) { ans[i] = max(ans[i], ans[i + 1]); } return ans; } };(code-box)

func findMaximums(nums []int) []int { n := len(nums) left := make([]int, n) right := make([]int, n) for i := range left { left[i], right[i] = -1, n } stk := []int{} for i, x := range nums { for len(stk) > 0 && nums[stk[len(stk)-1]] >= x { stk = stk[:len(stk)-1] } if len(stk) > 0 { left[i] = stk[len(stk)-1] } stk = append(stk, i) } stk = []int{} for i := n - 1; i >= 0; i-- { x := nums[i] for len(stk) > 0 && nums[stk[len(stk)-1]] >= x { stk = stk[:len(stk)-1] } if len(stk) > 0 { right[i] = stk[len(stk)-1] } stk = append(stk, i) } ans := make([]int, n) for i := range ans { m := right[i] - left[i] - 1 ans[m-1] = max(ans[m-1], nums[i]) } for i := n - 2; i >= 0; i-- { ans[i] = max(ans[i], ans[i+1]) } return ans }(code-box)