Subarray with elements greater than varying threshold

Array Stack Union-Find Monotonic Stack

45.3% acceptance

Feb 25, 2026

611

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn valid_subarray_size(nums: Vec<i32>, threshold: i32) -> i32 {
    let n = nums.len();
    let mut left = vec![-1i32; n];
    let mut right = vec![n as i32; n];
    let mut stack: Vec<usize> = vec![];

    for i in 0..n {
      while !stack.is_empty() && nums[*stack.last().unwrap()] >= nums[i] {
        let top = stack.pop().unwrap();
        right[top] = i as i32;
      }
      left[i] = stack.last().map_or(-1, |&x| x as i32);
      stack.push(i);
    }

    for i in 0..n {
      let k = right[i] - left[i] - 1;
      if nums[i] as i64 * k as i64 > threshold as i64 {
        return k;
      }
    }
    -1
  }
}