Formatted question description: https://leetcode.ca/all/2334.html

2334. Subarray With Elements Greater Than Varying Threshold

• Difficulty: Hard.
• Related Topics: Array, Stack, Union Find, Monotonic Stack.
• Similar Questions: Maximum Subarray Min-Product, Smallest K-Length Subsequence With Occurrences of a Letter, K Divisible Elements Subarrays.

Problem

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 <= 105

• 1 <= nums[i], threshold <= 109

Solution

• class Solution {
public int validSubarraySize(int[] nums, int threshold) {
int n = nums.length;
int[] min = new int[n];
// base case
TreeSet<Integer> dead = new TreeSet<>(Arrays.asList(n, -1));
PriorityQueue<Integer> maxheap = new PriorityQueue<>(Comparator.comparingInt(o -> -min[o]));
for (int i = 0; i < n; i++) {
min[i] = threshold / nums[i] + 1;
if (min[i] > nums.length) {
} else {
maxheap.offer(i);
}
}
while (!maxheap.isEmpty()) {
int cur = maxheap.poll();
// widest open range < minimum required length, this index is also bad.
} else {
// otherwise we've found it!
return min[cur];
}
}
return -1;
}
}

############

class Solution {
public int validSubarraySize(int[] nums, int threshold) {
int n = nums.length;
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(left, -1);
Arrays.fill(right, n);
Deque<Integer> stk = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
int v = nums[i];
while (!stk.isEmpty() && nums[stk.peek()] >= v) {
stk.pop();
}
if (!stk.isEmpty()) {
left[i] = stk.peek();
}
stk.push(i);
}
stk.clear();
for (int i = n - 1; i >= 0; --i) {
int v = nums[i];
while (!stk.isEmpty() && nums[stk.peek()] >= v) {
stk.pop();
}
if (!stk.isEmpty()) {
right[i] = stk.peek();
}
stk.push(i);
}
for (int i = 0; i < n; ++i) {
int v = nums[i];
int k = right[i] - left[i] - 1;
if (v > threshold / k) {
return k;
}
}
return -1;
}
}

• class Solution:
def validSubarraySize(self, nums: List[int], threshold: int) -> int:
n = len(nums)
left = [-1] * n
right = [n] * n
stk = []
for i, v in enumerate(nums):
while stk and nums[stk[-1]] >= v:
stk.pop()
if stk:
left[i] = stk[-1]
stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
while stk and nums[stk[-1]] >= nums[i]:
stk.pop()
if stk:
right[i] = stk[-1]
stk.append(i)
for i, v in enumerate(nums):
k = right[i] - left[i] - 1
if v > threshold // k:
return k
return -1

############

# 2334. Subarray With Elements Greater Than Varying Threshold
# https://leetcode.com/problems/subarray-with-elements-greater-than-varying-threshold

class Solution:
def validSubarraySize(self, nums: List[int], threshold: int) -> int:
n = len(nums)
prevSmaller = [-1] * n
nextSmaller = [n] * n

stack = []
for i, x in enumerate(nums):
while stack and x < nums[stack[-1]]:
nextSmaller[stack.pop()] = i
stack.append(i)

stack = []
for i in range(n - 1, -1,- 1):
while stack and nums[i] < nums[stack[-1]]:
prevSmaller[stack.pop()] = i
stack.append(i)

for i, x in enumerate(nums):
left, right = prevSmaller[i], nextSmaller[i]

N = right - left - 1

if x > threshold // N:
return N

return -1


• class Solution {
public:
int validSubarraySize(vector<int>& nums, int threshold) {
int n = nums.size();
vector<int> left(n, -1);
vector<int> right(n, n);
stack<int> stk;
for (int i = 0; i < n; ++i) {
int v = nums[i];
while (!stk.empty() && nums[stk.top()] >= v) stk.pop();
if (!stk.empty()) left[i] = stk.top();
stk.push(i);
}
stk = stack<int>();
for (int i = n - 1; ~i; --i) {
int v = nums[i];
while (!stk.empty() && nums[stk.top()] >= v) stk.pop();
if (!stk.empty()) right[i] = stk.top();
stk.push(i);
}
for (int i = 0; i < n; ++i) {
int v = nums[i];
int k = right[i] - left[i] - 1;
if (v > threshold / k) return k;
}
return -1;
}
};

• func validSubarraySize(nums []int, threshold int) int {
n := len(nums)
left := make([]int, n)
right := make([]int, n)
for i := range left {
left[i] = -1
right[i] = n
}
var stk []int
for i, v := range nums {
for len(stk) > 0 && nums[stk[len(stk)-1]] >= v {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
left[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
stk = []int{}
for i := n - 1; i >= 0; i-- {
v := nums[i]
for len(stk) > 0 && nums[stk[len(stk)-1]] >= v {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
right[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
for i, v := range nums {
k := right[i] - left[i] - 1
if v > threshold/k {
return k
}
}
return -1
}


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).