# Subarray With Elements Greater Than Varying Threshold
**Difficulty:** HARD
[External](https://leetcode.com/problems/subarray-with-elements-greater-than-varying-threshold)
Canonical: https://scaleengineer.com/dsa/problems/subarray-with-elements-greater-than-varying-threshold
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [instabase](https://scaleengineer.com/companies/instabase)
---
## 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`

# Approaches
## Brute Force with Optimization
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.
**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.
**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.
### Explanation
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:
1. Iterate through each possible starting index `i` from `0` to `n-1`.
2. For each `i`, initialize `minVal = nums[i]`.
3. Start an inner loop for the ending index `j` from `i` to `n-1`.
4. In the inner loop, update `minVal = Math.min(minVal, nums[j])`.
5. Calculate the length of the current subarray: `k = j - i + 1`.
6. Check if `(long)minVal * k > threshold`. This is a more robust way to check `minVal > threshold / k`.
7. If the condition is true, a valid subarray has been found. Return its length `k`.
8. If the loops finish without returning, no valid subarray exists. Return `-1`.

```java
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;
    }
}
```
### Algorithm
- Use two nested loops to iterate through all possible subarrays. The outer loop with index `i` determines the start of the subarray, and the inner loop with index `j` determines the end.
- For each subarray `nums[i...j]`, we need to find its minimum element `minVal` and its length `k = 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 `j` increases for a fixed `i`).
- For each subarray, check if the condition `minVal > threshold / k` is 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 return `k`.
- If the loops complete without finding any such subarray, it means no solution exists, so we return -1.

## Disjoint Set Union (DSU) with Sorting
This approach cleverly reframes the problem by iterating through the numbers from largest to smallest. It uses a Disjoint Set Union (DSU) data structure to efficiently track and merge contiguous segments of numbers that are all above a certain value. For each number, it checks if the segment it belongs to can form a valid subarray.
**Time:** O(n log n), where n is the length of `nums`. The sorting step is the bottleneck. The DSU operations in the loop take O(n * α(n)), which is nearly linear. · **Space:** O(n) to store the DSU parent and size arrays, the sorted indices array, and the visited array.
**Pros:** Much more efficient than the brute-force approach.; Guaranteed to find a solution if one exists.
**Cons:** More complex to implement compared to the brute-force approach.; The O(n log n) time complexity is not the most optimal solution.
### Explanation
Instead of checking every subarray, we can iterate through each element `nums[i]` and consider it as the minimum element of a potential subarray. The condition to check is `nums[i] > threshold / k`, where `k` is the length of this subarray.

To do this efficiently, we process elements from largest to smallest. This ensures that when we consider an element `val` at index `idx`, any other elements we have already processed (and formed segments with) have values greater than or equal to `val`. A Disjoint Set Union (DSU) data structure is ideal for tracking the size of these dynamically merging contiguous segments.

Here is the detailed algorithm:
1. Create an array of indices `0, 1, ..., n-1`.
2. Sort this index array based on the values in `nums` in descending order. This way, we process indices corresponding to larger `nums` values first.
3. Initialize a DSU structure of size `n` and a `visited` boolean array of size `n`.
4. Iterate through the sorted indices `id`:
   a. Mark `visited[id]` as true.
   b. Check the left neighbor `id-1`. If `id > 0` and `visited[id-1]` is true, perform `dsu.union(id, id-1)`.
   c. Check the right neighbor `id+1`. If `id < n-1` and `visited[id+1]` is true, perform `dsu.union(id, id+1)`.
   d. Get the size of the merged component containing `id`: `k = dsu.getSize(id)`.
   e. Check if `(long)nums[id] * k > threshold`. If this holds, we've found a subarray of length `k` where every element is at least `nums[id]`, satisfying the condition. Return `k`.
5. If the loop finishes, return -1.

```java
class Solution {
    class DSU {
        private int[] parent;
        private int[] sz;
        public DSU(int n) {
            parent = new int[n];
            sz = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                sz[i] = 1;
            }
        }
        public int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }
        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                if (sz[rootI] < sz[rootJ]) {
                    int temp = rootI;
                    rootI = rootJ;
                    rootJ = temp;
                }
                parent[rootJ] = rootI;
                sz[rootI] += sz[rootJ];
            }
        }
        public int getSize(int i) {
            return sz[find(i)];
        }
    }

    public int validSubarraySize(int[] nums, int threshold) {
        int n = nums.length;
        Integer[] ids = new Integer[n];
        for (int i = 0; i < n; i++) {
            ids[i] = i;
        }
        Arrays.sort(ids, (a, b) -> Integer.compare(nums[b], nums[a]));

        DSU dsu = new DSU(n);
        boolean[] visited = new boolean[n];

        for (int id : ids) {
            visited[id] = true;
            if (id > 0 && visited[id - 1]) {
                dsu.union(id, id - 1);
            }
            if (id < n - 1 && visited[id + 1]) {
                dsu.union(id, id + 1);
            }
            int k = dsu.getSize(id);
            if ((long) nums[id] * k > threshold) {
                return k;
            }
        }
        return -1;
    }
}
```
### Algorithm
- The core idea is to process elements in descending order of their values. For each value `v`, we consider it as the potential minimum of a subarray.
- Create pairs of `(value, index)` and sort them in descending order of `value`.
- Initialize a Disjoint Set Union (DSU) data structure to manage contiguous segments of processed elements. Each index starts in its own set of size 1.
- Iterate through the sorted `(val, idx)` pairs:
  - Mark the current index `idx` as processed (e.g., using a `visited` array).
  - Check its neighbors (`idx-1` and `idx+1`). If a neighbor has already been processed, merge the sets of `idx` and the neighbor using the DSU's `union` operation.
  - After merging, find the size `k` of the new contiguous segment containing `idx`.
  - This segment represents a subarray of length `k` where all elements are at least `val`.
  - Check if `(long)val * k > threshold`. If true, we have found a valid subarray of length `k`, so we return `k`.
- If the loop completes, no solution was found, so return -1.

## Monotonic Stack
This optimal approach uses a monotonic stack to efficiently determine, for each element `nums[i]`, the scope of the subarray where `nums[i]` acts as the minimum. By finding the nearest smaller elements on both sides (`prevSmaller` and `nextSmaller`), we can calculate the length `k` of this subarray and check the condition `nums[i] * k > threshold` in linear time.
**Time:** O(n). Each of the three passes (computing `prevSmaller`, `nextSmaller`, and checking the condition) takes linear time. Each element is pushed onto and popped from the stack at most once. · **Space:** O(n) to store the `prevSmaller` and `nextSmaller` arrays, as well as the stack used during computation.
**Pros:** Optimal time complexity of O(n).; Provides a deterministic and efficient way to check all relevant candidate subarrays without redundant computations.
**Cons:** The logic can be less intuitive to grasp compared to other approaches.; Requires O(n) extra space, which might be a concern for extremely large n under strict memory constraints.
### Explanation
The most efficient solution relies on a key insight: for any valid subarray, there must be a minimum element. We can iterate through each element `nums[i]` and treat it as the minimum of a potential candidate subarray. For a fixed minimum `nums[i]`, the condition `nums[i] > threshold / k` is easiest to satisfy when `k` is as large as possible.

The largest subarray for which `nums[i]` is the minimum is bounded by the first smaller element to its left and the first smaller element to its right. We can find these boundaries for all elements in O(n) time using a monotonic stack.

Here is the algorithm:
1.  **Compute `prevSmaller` array**: Create an array `prevSmaller` of size `n`. Iterate from `i = 0` to `n-1`. Use a monotonically increasing stack (of indices) to find the index of the first element to the left of `i` that is smaller than `nums[i]`. If no such element exists, store -1.
2.  **Compute `nextSmaller` array**: Similarly, create `nextSmaller` array. Iterate from `i = n-1` to `0` and use a monotonic stack to find the index of the first element to the right of `i` that is smaller than `nums[i]`. If none exists, store `n`.
3.  **Check Condition**: Iterate from `i = 0` to `n-1`. For each `i`:
    a. Calculate the length of the subarray where `nums[i]` is the minimum: `k = nextSmaller[i] - prevSmaller[i] - 1`.
    b. If `k > 0`, check if `(long)nums[i] * k > threshold`.
    c. If the condition is true, we have found a valid subarray of length `k`. Return `k`.
4.  If the loop completes, no valid subarray was found. Return -1.

```java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int validSubarraySize(int[] nums, int threshold) {
        int n = nums.length;
        int[] prevSmaller = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        // Find previous smaller element for each element
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            prevSmaller[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        stack.clear();
        int[] nextSmaller = new int[n];

        // Find next smaller element for each element
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            nextSmaller[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        // Check the condition for each potential subarray
        for (int i = 0; i < n; i++) {
            int k = nextSmaller[i] - prevSmaller[i] - 1;
            if (k > 0) {
                if ((long) nums[i] * k > threshold) {
                    return k;
                }
            }
        }

        return -1;
    }
}
```
### Algorithm
- For each element `nums[i]`, we find the largest possible subarray for which `nums[i]` is the minimum element.
- The boundaries of this subarray are determined by the `prevSmaller[i]` (index of the first element to the left of `i` that is smaller than `nums[i]`) and `nextSmaller[i]` (index of the first element to the right of `i` that is smaller than `nums[i]`).
- The length of this largest subarray is `k = nextSmaller[i] - prevSmaller[i] - 1`.
- For this subarray, the condition becomes `nums[i] > threshold / k`. If this holds, we have found a valid subarray of length `k` and can return `k`.
- The `prevSmaller` and `nextSmaller` arrays can be computed efficiently in O(n) time using a monotonic stack.
- We can perform two passes to compute these arrays and a third pass to check the condition, or combine the logic into a more optimized single pass.

# Solutions
### Java

```java
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];
  }
}

```

### CPP

```cpp
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 ]; } };
```

### Python

```python
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

```