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 thesize 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.

Examples

Example 1

1
2
3
4

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

1
2
3
4
5
6

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 <= 10^5
  • 1 <= nums[i], threshold <= 10^9

Solution

Method 1 - Monotonic Stack (Find Maximum Length Interval)

Intuition

For each element, we want to find the largest subarray where it is the minimum. For each such subarray, if the minimum element is greater than threshold / length, then that length is a valid answer. We can use a monotonic stack to find the left and right bounds for each element as the minimum.

Approach

  1. For each index, find the previous and next smaller elements using a monotonic stack.
  2. For each index, compute the length of the interval where nums[i] is the minimum.
  3. If nums[i] > threshold / length, return length (any such length is valid).
  4. If no such subarray exists, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
    int validSubarraySize(vector<int>& nums, int threshold) {
        int n = nums.size();
        vector<int> left(n, -1), right(n, n);
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && nums[st.top()] >= nums[i]) {
                right[st.top()] = i;
                st.pop();
            }
            if (!st.empty()) left[i] = st.top();
            st.push(i);
        }
        for (int i = 0; i < n; ++i) {
            int len = right[i] - left[i] - 1;
            if (nums[i] > threshold / len) return len;
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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 }
    for i := range right { right[i] = n }
    st := []int{}
    for i := 0; i < n; i++ {
        for len(st) > 0 && nums[st[len(st)-1]] >= nums[i] {
            right[st[len(st)-1]] = i
            st = st[:len(st)-1]
        }
        if len(st) > 0 { left[i] = st[len(st)-1] }
        st = append(st, i)
    }
    for i := 0; i < n; i++ {
        l := right[i] - left[i] - 1
        if nums[i] > threshold/l { return l }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;
class Solution {
    public int validSubarraySize(int[] nums, int threshold) {
        int n = nums.length;
        int[] left = new int[n], right = new int[n];
        Arrays.fill(left, -1);
        Arrays.fill(right, n);
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            while (!st.isEmpty() && nums[st.peek()] >= nums[i]) {
                right[st.pop()] = i;
            }
            if (!st.isEmpty()) left[i] = st.peek();
            st.push(i);
        }
        for (int i = 0; i < n; ++i) {
            int len = right[i] - left[i] - 1;
            if (nums[i] > threshold / len) return len;
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

fun validSubarraySize(nums: IntArray, threshold: Int): Int {
    val n = nums.size
    val left = IntArray(n) { -1 }
    val right = IntArray(n) { n }
    val st = ArrayDeque<Int>()
    for (i in 0 until n) {
        while (st.isNotEmpty() && nums[st.last()] >= nums[i]) {
            right[st.removeLast()] = i
        }
        if (st.isNotEmpty()) left[i] = st.last()
        st.addLast(i)
    }
    for (i in 0 until n) {
        val len = right[i] - left[i] - 1
        if (nums[i] > threshold / len) return len
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def validSubarraySize(nums, threshold):
    n = len(nums)
    left = [-1] * n
    right = [n] * n
    st = []
    for i in range(n):
        while st and nums[st[-1]] >= nums[i]:
            right[st.pop()] = i
        if st:
            left[i] = st[-1]
        st.append(i)
    for i in range(n):
        l = right[i] - left[i] - 1
        if nums[i] > threshold // l:
            return l
    return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

pub fn valid_subarray_size(nums: Vec<i32>, threshold: i32) -> i32 {
    let n = nums.len();
    let mut left = vec![-1; n];
    let mut right = vec![n as i32; n];
    let mut st = Vec::new();
    for i in 0..n {
        while let Some(&top) = st.last() {
            if nums[top] >= nums[i] {
                right[top] = i as i32;
                st.pop();
            } else { break; }
        }
        if let Some(&top) = st.last() { left[i] = top as i32; }
        st.push(i);
    }
    for i in 0..n {
        let len = right[i] - left[i] - 1;
        if nums[i] as i64 > threshold as i64 / len as i64 { return len; }
    }
    -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

function validSubarraySize(nums: number[], threshold: number): number {
    const n = nums.length;
    const left = Array(n).fill(-1);
    const right = Array(n).fill(n);
    const st: number[] = [];
    for (let i = 0; i < n; i++) {
        while (st.length && nums[st[st.length-1]] >= nums[i]) {
            right[st.pop()!] = i;
        }
        if (st.length) left[i] = st[st.length-1];
        st.push(i);
    }
    for (let i = 0; i < n; i++) {
        const len = right[i] - left[i] - 1;
        if (nums[i] > Math.floor(threshold / len)) return len;
    }
    return -1;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)