We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Subarray With Elements Greater Than Varying Threshold

Number: 2419

Difficulty: Hard

Paid? No

Companies: TikTok, Amazon, Google

Problem Description

Given an integer array nums and an integer threshold, find any contiguous subarray (of length k) such that every element in the subarray is greater than threshold/k. In other words, if m is the minimum element in the subarray then we require m > threshold/k. Return the size k of any subarray that satisfies the condition or -1 if no valid subarray exists.

Key Insights

  • The “hard” part of the problem is that the required condition depends on the subarray’s length: each element must be > threshold/k.
  • For any contiguous subarray, the “bottleneck” is its minimum element; if the minimum element m satisfies m > threshold/k then all other elements (which are ≥ m) will also satisfy it.
  • Instead of checking every possible subarray length (which would be too slow), we compute for each element the maximum contiguous block in which it is the minimum. This uses a “monotonic stack” approach, similar to the largest rectangle in histogram problem.
  • For a candidate element with value m that is the minimum over a contiguous subarray of maximum length L, note that any subarray containing that element and contained in that block will have minimum at least m.
  • The subarray’s requirement m > threshold/k can be rearranged as k > threshold/m. Thus the smallest valid window length using m as the minimum is k_min = floor(threshold/m) + 1.
  • If L (the maximum window length for which m remains the minimum) is at least k_min, then we can form a valid subarray of length k_min.

Space and Time Complexity

Time Complexity: O(n) – Each element is processed a constant number of times using the monotonic stack. Space Complexity: O(n) – For storing the left and right boundaries (and the stack).

Solution

The solution uses a monotonic stack to precompute for every index the number of contiguous elements to the left and right (including the index itself) that are greater than or equal to nums[i]. This gives the maximum subarray length where nums[i] is the minimum element. Then, for each element with value m = nums[i], we calculate the smallest possible subarray length where m can be the minimum and the condition would hold; that is k_min = floor(threshold/m) + 1. If the maximum subarray length L (centered at i) is at least k_min, then such a subarray exists and k_min is a valid answer.

Code Solutions

# Python solution using monotonic stacks

def validSubarraySize(nums, threshold):
    n = len(nums)
    left = [0] * n  # left[i] stores count of contiguous elements (including self) to the left >= nums[i]
    right = [0] * n # right[i] stores count of contiguous elements (including self) to the right >= nums[i]
    
    stack = []
    # compute left counts
    for i in range(n):
        # while stack is not empty and current element is less than element at stack top
        while stack and nums[stack[-1]] > nums[i]:
            stack.pop()
        if stack:
            left[i] = i - stack[-1]
        else:
            left[i] = i + 1
        stack.append(i)
    
    stack = []
    # compute right counts (process in reverse)
    for i in range(n - 1, -1, -1):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        if stack:
            right[i] = stack[-1] - i
        else:
            right[i] = n - i
        stack.append(i)
    
    # Now for each index i, the maximum subarray length for which nums[i] is the minimum is:
    # L = left[i] + right[i] - 1
    # For a valid subarray using nums[i] as the minimum, we need:
    # nums[i] > threshold / k, which rearranges to k > threshold / nums[i]
    # Therefore, the smallest valid subarray length is k_min = (threshold // nums[i]) + 1
    result = -1
    for i in range(n):
        L = left[i] + right[i] - 1  # maximum window length where nums[i] is minimum
        # smallest possible subarray length candidate using nums[i] as minimum
        k_min = (threshold // nums[i]) + 1
        # if the window can support this length then return it
        if L >= k_min:
            return k_min
    return -1

# Example usage:
print(validSubarraySize([1,3,4,3,1], 6))  # Expected output: 3 (or any valid k)
print(validSubarraySize([6,5,6,5,8], 7))  # Expected output: could be 1,2,3,4 or 5
← Back to All Questions