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.
The sliding window technique allows efficient checking of consecutive subarrays. We will maintain a window of length k and slide it over the array. If every element within this window is greater than threshold/k, we can return k as the answer.
This solution loops over possible subarray lengths k from 1 to n. For each k, we calculate the required minimum value threshold/k. Then, we iterate over all possible subarray starts i and verify if each element in the subarray is greater than the required minimum. If such a subarray is found, we return its length k.
Time Complexity: O(n^2), as for each subarray length we might check each element in a maximal subarray.
Space Complexity: O(1), extra space used.
Using binary search, we can optimize which subarray lengths to check. By verifying subarrays of a potential length using a sliding window, we can narrow down the range of valid lengths.
This Java solution uses binary search over possible subarray lengths. By calling the helper function check(), it verifies if a valid subarray exists for the current middle length of the search range, updating the range accordingly.
Java
JavaScript
Time Complexity: O(n log n) due to binary search and sliding window check.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Sliding Window | Time Complexity: O(n^2), as for each subarray length we might check each element in a maximal subarray. |
| Binary Search with Sliding Window | Time Complexity: O(n log n) due to binary search and sliding window check. |
| Default Approach | — |
| 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 |
Biweekly Contest 82 | 2334. Subarray With Elements Greater Than Varying Threshold • codingMohan • 3,620 views views
Watch 6 more video solutions →Practice Subarray With Elements Greater Than Varying Threshold with our built-in code editor and test cases.
Practice on FleetCode