Question

Code

class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        
        # Firstly, we can compare the min_value for each sub_array to see if it satisfy the condition
        # Since threshold is constant, that mean the higher the k is, more likely the current element is greater than that
        # Hence find the longest sub_array for each element such that the element is the minimum

        n = len(nums)

        left_index = [i for i in range(n)]

        right_index = [i for i in range(n)]

        monotonic_stack = []
        # [[item, index]]
        # Actually can just add the index

        for i in range(n):
            while monotonic_stack and nums[i] <= monotonic_stack[-1][0]:
                monotonic_stack.pop()

            if len(monotonic_stack) == 0:
                left_index[i] = 0
            else:
                left_index[i] = monotonic_stack[-1][1] + 1

            monotonic_stack.append([nums[i], i])


        monotonic_stack = []
        for i in range(n - 1, -1, -1):
            while monotonic_stack and nums[i] <= monotonic_stack[-1][0]:
                monotonic_stack.pop()

            if len(monotonic_stack) == 0:
                right_index[i] = n - 1
            else:
                right_index[i] = monotonic_stack[-1][1] - 1

            monotonic_stack.append([nums[i], i])

        for i in range(n):
            k = right_index[i] - left_index[i] + 1

            if nums[i] > threshold / k:
                return k

        return -1