2334. Subarray With Elements Greater Than Varying Threshold LeetCode Solution
In this guide, you will get 2334. Subarray With Elements Greater Than Varying Threshold LeetCode Solution with the best time and space complexity. The solution to Subarray With Elements Greater Than Varying Threshold problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Subarray With Elements Greater Than Varying Threshold
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.
2334. Subarray With Elements Greater Than Varying Threshold LeetCode Solution in C++
class Solution {
public:
// Similar to 907. Sum of Subarray Minimums
int validSubarraySize(vector<int>& nums, int threshold) {
const int n = nums.size();
// prev[i] := the index k s.t. nums[k] is the previous minimum in nums[0..n)
vector<int> prev(n, -1);
// next[i] := the index k s.t. nums[k] is the next minimum in nums[i + 1..n)
vector<int> next(n, n);
stack<int> stack;
for (int i = 0; i < n; ++i) {
while (!stack.empty() && nums[stack.top()] > nums[i]) {
const int index = stack.top();
stack.pop();
next[index] = i;
}
if (!stack.empty())
prev[i] = stack.top();
stack.push(i);
}
for (int i = 0; i < n; ++i) {
// the number of `nums` in subarray containing nums[i] >= nums[i]
const int k = (i - prev[i]) + (next[i] - i) - 1;
if (nums[i] > threshold / static_cast<double>(k))
return k;
}
return -1;
}
}; /* code provided by PROGIEZ */
2334. Subarray With Elements Greater Than Varying Threshold LeetCode Solution in Java
class Solution {
// Similar to 907. Sum of Subarray Minimums
public int validSubarraySize(int[] nums, int threshold) {
final int n = nums.length;
long ans = 0;
// prev[i] := the index k s.t. nums[k] is the previous minimum in nums[0..n)
int[] prev = new int[n];
// next[i] := the index k s.t. nums[k] is the next minimum in nums[i + 1..n)
int[] next = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
Arrays.fill(prev, -1);
Arrays.fill(next, n);
for (int i = 0; i < nums.length; ++i) {
while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
final int index = stack.pop();
next[index] = i;
}
if (!stack.isEmpty())
prev[i] = stack.peek();
stack.push(i);
}
for (int i = 0; i < n; ++i) {
// the number of `nums` in subarray containing nums[i] >= nums[i]
final int k = (i - prev[i]) + (next[i] - i) - 1;
if (nums[i] > threshold / (double) k)
return k;
}
return -1;
}
} // code provided by PROGIEZ
2334. Subarray With Elements Greater Than Varying Threshold LeetCode Solution in Python
class Solution:
# Similar to 907. Sum of Subarray Minimums
def validSubarraySize(self, nums: list[int], threshold: int) -> int:
n = len(nums)
ans = 0
# prev[i] := the index k s.t. nums[k] is the previous minimum in nums[0..n)
prev = [-1] * n
# next[i] := the index k s.t. nums[k] is the next minimum in nums[i + 1..n)
next = [n] * n
stack = []
for i, a in enumerate(nums):
while stack and nums[stack[-1]] > a:
index = stack.pop()
next[index] = i
if stack:
prev[i] = stack[-1]
stack.append(i)
for i, (num, prevIndex, nextIndex) in enumerate(zip(nums, prev, next)):
k = (i - prevIndex) + (nextIndex - i) - 1
if num > threshold / k:
return k
return -1 # code by PROGIEZ
