Subarray With Elements Greater Than Varying Threshold
HardPrompt
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 <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
This approach systematically checks every possible contiguous subarray within the nums array. For each subarray, it finds the minimum element and the length, then verifies if the given condition min(subarray) > threshold / length is satisfied. It's the most straightforward, brute-force method.
Algorithm
- Use two nested loops to iterate through all possible subarrays. The outer loop with index
idetermines the start of the subarray, and the inner loop with indexjdetermines the end. - For each subarray
nums[i...j], we need to find its minimum elementminValand its lengthk = j - i + 1. - To avoid a third loop which would result in an O(n^3) solution, we can maintain the minimum value as we extend the subarray (i.e., as
jincreases for a fixedi). - For each subarray, check if the condition
minVal > threshold / kis met. To avoid floating-point arithmetic and potential precision issues, it's better to check the equivalent condition(long)minVal * k > threshold. - If the condition holds, we have found a valid subarray of length
k, and we can immediately returnk. - If the loops complete without finding any such subarray, it means no solution exists, so we return -1.
Walkthrough
The brute-force approach iterates through all possible starting and ending points of a subarray. For each subarray, it calculates its length and finds its minimum element, then checks if the condition is satisfied.
An initial naive implementation would use three nested loops: two for the subarray boundaries and one to find the minimum, leading to O(n³) complexity. We can optimize this by observing that as we extend a subarray nums[i...j] to nums[i...j+1], the new minimum is just the minimum of the old subarray's minimum and the new element nums[j+1]. This optimization reduces the complexity to O(n²).
Here is the algorithm for the optimized brute-force approach:
- Iterate through each possible starting index
ifrom0ton-1. - For each
i, initializeminVal = nums[i]. - Start an inner loop for the ending index
jfromiton-1. - In the inner loop, update
minVal = Math.min(minVal, nums[j]). - Calculate the length of the current subarray:
k = j - i + 1. - Check if
(long)minVal * k > threshold. This is a more robust way to checkminVal > threshold / k. - If the condition is true, a valid subarray has been found. Return its length
k. - If the loops finish without returning, no valid subarray exists. Return
-1.
class Solution { public int validSubarraySize(int[] nums, int threshold) { int n = nums.length; for (int i = 0; i < n; i++) { int minVal = nums[i]; for (int j = i; j < n; j++) { minVal = Math.min(minVal, nums[j]); int k = j - i + 1; if ((long) minVal * k > threshold) { return k; } } } return -1; }}Complexity
Time
O(n^2), where n is the number of elements in `nums`. The nested loops result in a quadratic number of checks.
Space
O(1) extra space, as we only use a few variables to store the loop indices and the running minimum.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space, making it very memory-efficient.
Cons
The O(n^2) time complexity is too slow for the given constraints (n up to 10^5) and will result in a Time Limit Exceeded (TLE) error on most platforms.
Solutions
Solution
class Solution {private int[] p;private int[] size;public int validSubarraySize(int[] nums, int threshold) { int n = nums.length; p = new int[n]; size = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; size[i] = 1; } int[][] arr = new int[n][2]; for (int i = 0; i < n; ++i) { arr[i][0] = nums[i]; arr[i][1] = i; } Arrays.sort(arr, (a, b)->b[0] - a[0]); boolean[] vis = new boolean[n]; for (int[] e : arr) { int v = e[0], i = e[1]; if (i > 0 && vis[i - 1]) { merge(i, i - 1); } if (i < n - 1 && vis[i + 1]) { merge(i, i + 1); } if (v > threshold / size[find(i)]) { return size[find(i)]; } vis[i] = true; } return -1; }private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; }private void merge(int a, int b) { int pa = find(a), pb = find(b); if (pa == pb) { return; } p[pa] = pb; size[pb] += size[pa]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.