{x}
blog image

Maximum of Minimum Values in All Subarrays

Solution Explanation

This problem asks to find the maximum of minimum values in all subarrays of size k for each k from 1 to n, where n is the length of the input array nums. A brute-force approach would have a time complexity of O(n³), which is inefficient for large inputs. The optimal solution uses a monotonic stack to achieve O(n) time complexity.

Monotonic Stack Approach:

The core idea is to use two monotonic stacks, one increasing and one decreasing, to efficiently find the left and right boundaries for each element such that the element is the minimum within that range.

  1. Finding Left and Right Boundaries:

    • We iterate through the nums array twice: once from left to right and once from right to left.
    • For each element, we use a stack to maintain a monotonically increasing (or decreasing) sequence. If a smaller (or larger) element is encountered, we pop elements from the stack until we find a smaller (or larger) element or the stack becomes empty. This ensures that when we encounter an element, the top of the stack represents the closest element to the left (or right) that is smaller (or larger) than the current element.
    • left[i] stores the index of the nearest smaller element to the left of nums[i]. If no such element exists, left[i] is -1.
    • right[i] stores the index of the nearest smaller element to the right of nums[i]. If no such element exists, right[i] is n.

  2. Calculating Maximum Minimums:

    • For each nums[i], the length of the subarray where nums[i] is the minimum is right[i] - left[i] - 1.
    • We use ans[right[i] - left[i] - 2] to store the maximum minimum value for subarrays of length right[i] - left[i] - 1. We update this value with max(ans[right[i] - left[i] - 2], nums[i]).
    • Finally, we iterate through ans from right to left, applying ans[i] = max(ans[i], ans[i + 1]). This step ensures that ans[i] correctly stores the maximum of the minimum values for all subarrays of size i + 1.

Time Complexity: O(n) - Each element is pushed and popped from the stack at most once. Space Complexity: O(n) - To store left, right, and ans arrays.

Code in Different Languages

Python:

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

Java:

import java.util.*;
 
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;
    }
}

C++:

#include <vector>
#include <stack>
#include <algorithm>
 
using namespace std;
 
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;
    }
};

Go:

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
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

These codes all implement the same monotonic stack algorithm, demonstrating its efficiency and adaptability across different programming languages. Remember to handle edge cases and potential errors appropriately in a production environment.