Skip to content

2334. Subarray With Elements Greater Than Varying Threshold

Difficulty Topics

Description

You are given an integer array nums and an integer threshold.

Find any subarray of nums of length k such that every element in the subarray is greater than threshold / k.

Return the size of any such subarray. If there is no such subarray, return -1.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,3,4,3,1], threshold = 6
Output: 3
Explanation: The subarray [3,4,3] has a size of 3, and every element is greater than 6 / 3 = 2.
Note that this is the only valid subarray.

Example 2:

Input: nums = [6,5,6,5,8], threshold = 7
Output: 1
Explanation: The subarray [8] has a size of 1, and 8 > 7 / 1 = 7. So 1 is returned.
Note that the subarray [6,5] has a size of 2, and every element is greater than 7 / 2 = 3.5. 
Similarly, the subarrays [6,5,6], [6,5,6,5], [6,5,6,5,8] also satisfy the given conditions.
Therefore, 2, 3, 4, or 5 may also be returned.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i], threshold <= 109

Solution

subarray-with-elements-greater-than-varying-threshold.py
class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        prevSmaller = [-1] * n
        nextSmaller = [n] * n

        stack = []
        for i, x in enumerate(nums):
            while stack and x < nums[stack[-1]]:
                nextSmaller[stack.pop()] = i
            stack.append(i)

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

        for i, x in enumerate(nums):
            left, right = prevSmaller[i], nextSmaller[i]

            N = right - left - 1

            if x > threshold // N:
                return N

        return -1