LC-2334 Hard LeetCode

2334. Subarray With Elements Greater Than Varying Threshold

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 44% Topics: Array, Stack, Union Find, Monotonic Stack

Reading material

Arrays & Hashing 12 min Stacks & Queues 11 min Union–Find (DSU) 12 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

# mono stack
class Solution(object):
    def validSubarraySize(self, nums, threshold):
        """
        :type nums: List[int]
        :type threshold: int
        :rtype: int
        """
        stk = [-1]
        for i in xrange(len(nums)+1):
            while stk[-1] != -1 and (i == len(nums) or nums[stk[-1]] >= nums[i]):
                if nums[stk.pop()]*((i-1)-stk[-1]) > threshold:
                    return (i-1)-stk[-1]
            stk.append(i)
        return -1

Solution from kamyu104/LeetCode-Solutions · MIT