Min Max Riddle

  • + 1 comment

    Python solution with a stack. You need to split solution in 2 parts:

    1. Go through the array and add to stack till the next number is smaller than the last value added to stack. When it happens you pop from the stack checking if value is higher than value in max windows array.

    2. You end up with array with maximum windows for some window lengths. You have to populate the missing values with values from the right using a logic that window length for bigger window is also at least maximum for a smaller window.

    def riddle(arr):
        max_win = [0 for i in range(len(arr))]
        arr = arr.copy() + [-1]
        stack = []
        for i in range(len(arr)):
            prev_i = i    
            while len(stack) > 0 and stack[-1][1] >= arr[i]:
                prev_i, value = stack.pop()
                window = i - prev_i - 1
                max_win[window] = max(max_win[window], value)
            stack.append((prev_i, arr[i]))
        for n in range(len(max_win)-2,0,-1):
            max_win[n] = max(max_win[n], max_win[n+1])
        return max_win
    

    `