Watch 7 video solutions for Subarray With Elements Greater Than Varying Threshold, a hard level problem involving Array, Stack, Union Find. This walkthrough by codingMohan has 3,620 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= nums[i], threshold <= 109Problem Overview: Given an integer array nums and a threshold, find a subarray of length k such that min(subarray) * k > threshold. Return any valid length k, or -1 if no such subarray exists.
Approach 1: Sliding Window Scan (O(n²) time, O(1) space)
Check subarrays of different lengths using a sliding window over the array. For each window size k, iterate through the array and track the minimum element inside the current window. If min * k > threshold, return k. The idea is straightforward: brute-force every possible window length and evaluate the constraint. This approach is easy to reason about but recalculates minimum values repeatedly, leading to quadratic time in the worst case.
Approach 2: Binary Search + Sliding Window Minimum (O(n log n) time, O(n) space)
Binary search the answer for the subarray length k. For each candidate length, run a sliding window across the array while maintaining the window minimum using a deque-based structure similar to a monotonic stack or monotonic queue. Each step checks whether windowMin * k > threshold. Binary search reduces the number of lengths you test from n to log n, while the deque maintains minimum values in amortized constant time.
Approach 3: Monotonic Stack Range Expansion (O(n) time, O(n) space)
The optimal observation treats each element as the minimum of some maximal subarray. Using a stack, compute the previous and next smaller elements for every index. This determines the largest range where that value remains the minimum. If the length of that range L satisfies nums[i] * L > threshold, the requirement holds and L is a valid answer. This transforms the problem into a classic monotonic stack boundary calculation, similar to largest-rectangle-in-histogram style problems.
Recommended for interviews: The monotonic stack solution is typically the expected optimal approach because it runs in linear time and demonstrates strong understanding of range boundaries and stack-based array processing. Starting with the sliding window idea shows you understand the condition, but reaching the stack optimization signals deeper algorithmic skill.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window Scan | O(n²) | O(1) | Small arrays or when demonstrating brute-force reasoning |
| Binary Search + Sliding Window Minimum | O(n log n) | O(n) | When binary searching the valid length while efficiently maintaining window minimums |
| Monotonic Stack Range Expansion | O(n) | O(n) | Optimal solution for large inputs and typical interview expectation |