# 2334. Subarray With Elements Greater Than Varying Threshold

## Description

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

## Solutions

• 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];
}
}

• using pii = pair<int, int>;

class Solution {
public:
vector<int> p;
vector<int> size;

int validSubarraySize(vector<int>& nums, int threshold) {
int n = nums.size();
p.resize(n);
for (int i = 0; i < n; ++i) p[i] = i;
size.assign(n, 1);
vector<pii> arr(n);
for (int i = 0; i < n; ++i) arr[i] = {nums[i], i};
sort(arr.begin(), arr.end());
vector<bool> vis(n);
for (int j = n - 1; ~j; --j) {
int v = arr[j].first, i = arr[j].second;
if (i && vis[i - 1]) merge(i, i - 1);
if (j < n - 1 && vis[i + 1]) merge(i, i + 1);
if (v > threshold / size[find(i)]) return size[find(i)];
vis[i] = true;
}
return -1;
}

int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

void merge(int a, int b) {
int pa = find(a), pb = find(b);
if (pa == pb) return;
p[pa] = pb;
size[pb] += size[pa];
}
};

• class Solution:
def validSubarraySize(self, nums: List[int], threshold: int) -> int:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]

def merge(a, b):
pa, pb = find(a), find(b)
if pa == pb:
return
p[pa] = pb
size[pb] += size[pa]

n = len(nums)
p = list(range(n))
size = [1] * n
arr = sorted(zip(nums, range(n)), reverse=True)
vis = [False] * n
for v, i in arr:
if i and vis[i - 1]:
merge(i, i - 1)
if i < n - 1 and vis[i + 1]:
merge(i, i + 1)
if v > threshold // size[find(i)]:
return size[find(i)]
vis[i] = True
return -1


• func validSubarraySize(nums []int, threshold int) int {
n := len(nums)
p := make([]int, n)
size := make([]int, n)
for i := range p {
p[i] = i
size[i] = 1
}
var find func(int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
merge := func(a, b int) {
pa, pb := find(a), find(b)
if pa == pb {
return
}
p[pa] = pb
size[pb] += size[pa]
}

arr := make([][]int, n)
for i, v := range nums {
arr[i] = []int{v, i}
}
sort.Slice(arr, func(i, j int) bool {
return arr[i][0] > arr[j][0]
})
vis := make([]bool, n)
for _, e := range arr {
v, i := e[0], 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
}