2334. Subarray > Varying Threshold Solution

The 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 <= 10⁵
1 <= nums[i], threshold <= 10⁹

Approach overview

Problem Overview: Given an integer array nums and a threshold, find a subarray of length k such that min(subarray) * k > threshold. Return any valid length k, or -1 if no such subarray exists.

Approach 1: Sliding Window Scan (O(n²) time, O(1) space)

Check subarrays of different lengths using a sliding window over the array. For each window size k, iterate through the array and track the minimum element inside the current window. If min * k > threshold, return k. The idea is straightforward: brute-force every possible window length and evaluate the constraint. This approach is easy to reason about but recalculates minimum values repeatedly, leading to quadratic time in the worst case.

Approach 2: Binary Search + Sliding Window Minimum (O(n log n) time, O(n) space)

Binary search the answer for the subarray length k. For each candidate length, run a sliding window across the array while maintaining the window minimum using a deque-based structure similar to a monotonic stack or monotonic queue. Each step checks whether windowMin * k > threshold. Binary search reduces the number of lengths you test from n to log n, while the deque maintains minimum values in amortized constant time.

Approach 3: Monotonic Stack Range Expansion (O(n) time, O(n) space)

The optimal observation treats each element as the minimum of some maximal subarray. Using a stack, compute the previous and next smaller elements for every index. This determines the largest range where that value remains the minimum. If the length of that range L satisfies nums[i] * L > threshold, the requirement holds and L is a valid answer. This transforms the problem into a classic monotonic stack boundary calculation, similar to largest-rectangle-in-histogram style problems.

Recommended for interviews: The monotonic stack solution is typically the expected optimal approach because it runs in linear time and demonstrates strong understanding of range boundaries and stack-based array processing. Starting with the sliding window idea shows you understand the condition, but reaching the stack optimization signals deeper algorithmic skill.

Approach 1: Sliding Window

The sliding window technique allows efficient checking of consecutive subarrays. We will maintain a window of length k and slide it over the array. If every element within this window is greater than threshold/k, we can return k as the answer.

Python

def subarray_with_threshold(nums, threshold):
    n = len(nums)
    for k in range(1, n+1):
        required_minimum = threshold / k
        for i in range(n-k+1):
            if all(num > required_minimum for num in nums[i:i+k]):
                return k
    return -1

C++

#include <vector>
#include <cmath>
using namespace std;

int subarray_with_threshold(vector<int>& nums, int threshold) {
    int n = nums.size();
    for (int k = 1; k <= n; ++k) {
        double required_minimum = static_cast<double>(threshold) / k;
        for (int i = 0; i <= n - k; ++i) {
            bool valid = true;
            for (int j = i; j < i + k; ++j) {
                if (nums[j] <= required_minimum) {
                    valid = false;
                    break;
                }
            }
            if (valid)
                return k;
        }
    }
    return -1;
}

This solution loops over possible subarray lengths k from 1 to n. For each k, we calculate the required minimum value threshold/k. Then, we iterate over all possible subarray starts i and verify if each element in the subarray is greater than the required minimum. If such a subarray is found, we return its length k.

Complexity

Time Complexity: O(n^2), as for each subarray length we might check each element in a maximal subarray.
Space Complexity: O(1), extra space used.

Try this approach in the editor

Approach 2: Binary Search with Sliding Window

Using binary search, we can optimize which subarray lengths to check. By verifying subarrays of a potential length using a sliding window, we can narrow down the range of valid lengths.

Java

public class Solution {
    public int subarrayWithThreshold(int[] nums, int threshold) {
        int left = 1, right = nums.length, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (check(nums, threshold, mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    private boolean check(int[] nums, int threshold, int k) {
        double required = (double) threshold / k;
        for (int i = 0; i <= nums.length - k; i++) {
            boolean valid = true;
            for (int j = i; j < i + k; j++) {
                if (nums[j] <= required) {
                    valid = false;
                    break;
                }
            }
            if (valid) return true;
        }
        return false;
    }
}

JavaScript

function subarrayWithThreshold(nums, threshold) {
    let left = 1, right = nums.length, ans = -1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (check(nums, threshold, mid)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;

    function check(nums, threshold, k) {
        const required = threshold / k;
        for (let i = 0; i <= nums.length - k; i++) {
            let valid = true;
            for (let j = i; j < i + k; j++) {
                if (nums[j] <= required) {
                    valid = false;
                    break;
                }
            }
            if (valid) return true;
        }
        return false;
    }
}

This Java solution uses binary search over possible subarray lengths. By calling the helper function check(), it verifies if a valid subarray exists for the current middle length of the search range, updating the range accordingly.

Complexity

Time Complexity: O(n log n) due to binary search and sliding window check.
Space Complexity: O(1).

Try this approach in the editor

Approach 3: Default Approach

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
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sliding Window	Time Complexity: O(n^2), as for each subarray length we might check each element in a maximal subarray. Space Complexity: O(1), extra space used.
Binary Search with Sliding Window	Time Complexity: O(n log n) due to binary search and sliding window check. Space Complexity: O(1).
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Sliding Window Scan	O(n²)	O(1)	Small arrays or when demonstrating brute-force reasoning
Binary Search + Sliding Window Minimum	O(n log n)	O(n)	When binary searching the valid length while efficiently maintaining window minimums
Monotonic Stack Range Expansion	O(n)	O(n)	Optimal solution for large inputs and typical interview expectation

Frequently asked questions

Is Subarray With Elements Greater Than Varying Threshold easy or hard?

The problem is classified as Hard because the key observation involves converting the condition into a range where an element remains the minimum. Recognizing the monotonic stack pattern and mapping it to range expansion makes the solution non-trivial for many candidates.

Subarray With Elements Greater Than Varying Threshold Python/Java solution

Python solutions typically implement the monotonic stack approach using a list as the stack and arrays for left/right boundaries. Java implementations follow the same logic using a Stack or ArrayDeque. Both versions achieve O(n) time and O(n) space complexity.

How to solve Subarray With Elements Greater Than Varying Threshold in O(n)?

Treat each element as the potential minimum of a subarray. Using a monotonic stack, compute the nearest smaller element to the left and right to determine the maximum span where that element remains the minimum. Let the span length be L; if nums[i] * L > threshold, return L. Each element is pushed and popped at most once, giving O(n) time.

What is the best approach for Subarray With Elements Greater Than Varying Threshold?

The most efficient solution uses a monotonic stack to compute the previous and next smaller element for each index. This reveals the maximum subarray length where a value remains the minimum. If nums[i] multiplied by that length exceeds the threshold, a valid subarray exists. This approach runs in O(n) time and O(n) space.

Is Subarray With Elements Greater Than Varying Threshold asked at Google/Amazon/Meta?

Problems involving monotonic stacks and subarray minimum ranges frequently appear in interviews at companies like Amazon, Google, and Meta. This question is closely related to classic interview problems such as Largest Rectangle in Histogram and Sum of Subarray Minimums.

What data structure is used in Subarray With Elements Greater Than Varying Threshold?

The key data structure is a monotonic stack that keeps indices in increasing order of values. It helps compute previous and next smaller elements efficiently. Some alternative solutions also use a deque for sliding window minimums during binary search checks.

What is the time complexity of Subarray With Elements Greater Than Varying Threshold?

The optimal algorithm runs in O(n) time using a monotonic stack to determine the span where each element is the minimum. Alternative implementations like binary search combined with sliding window minimum checks run in O(n log n) time.

Subarray With Elements Greater Than Varying Threshold solution and explanation

The problem

Approach overview

Approach 1: Sliding Window

Approach 2: Binary Search with Sliding Window

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Subarray With Elements Greater Than Varying Threshold solution and explanation

The problem

Approach overview

Approach 1: Sliding Window

Approach 2: Binary Search with Sliding Window

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems