Skip to content

2334. Subarray With Elements Greater Than Varying Threshold 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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