Problem statement

https://leetcode.com/problems/maximum-of-minimum-values-in-all-subarrays/

Solution 1

It is quite difficult problem in fact, it should be marked as hard and even among hards it is not the easiest one. One of the ways to solve this problem is to use dsu. Imagine that we have numbers arr = [1, 4, 2, 8, 5, 7]. Let us start from big numbers and add number by number, we have

_ _ _ _ _ _

_ _ _ 8 _ _

_ _ _ 8 _ 7

_ _ _ 8 5 7

_ 4 _ 8 5 7

_ 4 2 8 5 7

1 4 2 8 4 7

What we ask each time we add new number: what is the biggest size of group we have: for example when we have _ _ _ 8 5 7 we have group of size 3 and it means that there is window of size 3 with minimum value >= 5. If we look at the biggest groups, we will have 1, 1, 3, 3, 5, 6. It means, that we have answer [8, 5, 5, 2, 2, 1]: first element is always the biggest element in array. Then after we add 7 biggest length do not changed, so do nothing. Then we add 5 and now length is equal to 3, so we add 5, 5: until we have 3 elements in res. Then we add 4: nothing changes. Then we add 2, now we have group of size 5: so we add 2 two times. Finally we add 1 and we have group of size 6.

Note, that it is very useful to keep dsu data structure to be able quickly update our segments.

Complexity

It is O(n log n), because we sorted our data and then use dsu with path compression which is O(log n) applied n times. Space complexity is O(n).

Code

class DSU:
    def __init__(self):
        self.p = {}
        self.size = {}
        
    def add(self, x):
        self.p[x] = x
        self.size[x] = 1

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr
        self.size[yr] += self.size[xr]

class Solution:
    def findMaximums(self, arr):
        n = len(arr)
        dsu = DSU()
        res = []
        
        for x in sorted(range(n), key = lambda x: -arr[x]):
            dsu.add(x)
            if x-1 in dsu.p: dsu.union(x, x-1)
            if x+1 in dsu.p: dsu.union(x, x+1)
            size = dsu.size[dsu.find(x)]
            while len(res) < size:
                res += [arr[x]]

        return res

Solution 2

In fact, we can use problem 0352. Data Stream as Disjoint Intervals: this is exactly what we want do have and we need to keep length of the biggest interval.

Complexity

Time complexity is O(n log n), because we sort and space complexity is O(n).

Code

class SummaryRanges:
    def __init__(self):
        self.d1, self.d2 = {}, {}
        self.max_len = 0

    def addNum(self, v):
        i1 = self.d2.get(v - 1, -1)
        i2 = self.d1.get(v + 1, -1)
        lft, rgh = v - 1 in self.d2, v + 1 in self.d1
                
        if lft and rgh:
            self.d1[i1] = i2
            self.d2[i2] = i1
            self.max_len = max(self.max_len, i2-i1+1)
        elif lft and not rgh:
            self.d1[i1] = v
            self.d2[v] = i1
            self.max_len = max(self.max_len, v-i1+1)
        elif not lft and rgh:
            self.d2[i2] = v
            self.d1[v] = i2
            self.max_len = max(self.max_len, i2-v+1)
        else:
            self.d1[v] = v
            self.d2[v] = v
            self.max_len = max(self.max_len, 1)
            
        self.d2.pop(v - 1, None)
        self.d1.pop(v + 1, None)

    def getIntervals(self):
        return sorted([[i, self.d1[i]] for i in self.d1])
        

class Solution:
    def findMaximums(self, arr):
        n = len(arr)
        ranges = SummaryRanges()
        res = []
        
        for x in sorted(range(n), key = lambda x: -arr[x]):
            ranges.addNum(x)
            while len(res) < ranges.max_len:
                res += [arr[x]]

        return res

Solution 3

Finally, there is solution, using monotonic stack. The idea is: for each coming element nums[i], calculate L and R, the indices of the first smallest elements on the left and the right respectively. Then the answer of the queries from 1 to R-L+1 will be at least this element. It means that we can find for each value the biggest window we can have and then use accumulate maximum from the end to get answer.

Complexity

Time complexity is O(n), space is O(n).

Code

class Solution:
    def findMaximums(self, nums):
        n = len(nums)
        lft, rgh, res = [-1] * n, [n] * n, [-1]*n
       
        stack = []
        for i in range(n):
            while stack and nums[i] <= nums[stack[-1]]: stack.pop()
            if stack: lft[i] = stack[-1]
            stack.append(i)
            
        stack = []
        for i in range(n - 1, -1, -1):
            while stack and nums[i] <= nums[stack[-1]]: stack.pop()
            if stack: rgh[i] = stack[-1]
            stack.append(i)
            
        for i in range(n):
            ln = rgh[i] - lft[i] - 2
            res[ln] = max(res[ln], nums[i])
            
        return list(accumulate(res[::-1], max))[::-1]

Remark

I have one more idea how to solve this problem: we can start from the smallest numbers (like we did in solutions 1 and 2, but in opposite order) and now we need to keep the length of the biggest non-covered interval. We can put indexes in BST (SortedList) and then each time we put new, update lengths. I think complexity will be O(n log n) as well.