LeetCode 2334 - Subarray With Elements Greater Than Varying Threshold

LeetCode Problem 2334

Difficulty: 🔴 Hard
Topics: Array, Stack, Union-Find, Monotonic Stack

Solution

Problem Understanding

This problem asks us to find a contiguous subarray whose elements are all sufficiently large relative to the subarray length.

More specifically, for a subarray of length k, every element inside that subarray must satisfy:

$$\text{element} > \frac{\text{threshold}}{k}$$

We are allowed to return the size k of any valid subarray. If no such subarray exists, we return -1.

The important detail is that the condition applies to every element in the subarray. That means the smallest element inside the subarray determines whether the entire subarray is valid. If the minimum value in a subarray is m, then the condition becomes:

$$m > \frac{\text{threshold}}{k}$$

Rearranging this gives:

$$m \times k > \text{threshold}$$

or equivalently:

$$k > \frac{\text{threshold}}{m}$$

This observation is the key to the optimal solution.

The input constraints are large:

• nums.length can be up to 10^5
• nums[i] and threshold can be up to 10^9

These constraints immediately rule out expensive approaches such as checking all subarrays. An O(n^2) solution would time out for arrays of size 100000.

Several edge cases are important:

• Arrays where no valid subarray exists
• Arrays where a single element already satisfies the condition
• Arrays with repeated values
• Strictly increasing or strictly decreasing arrays
• Cases where the valid subarray spans almost the entire array
• Cases where the minimum element appears multiple times

The problem guarantees that the array is non-empty and all values are positive integers, which simplifies some reasoning because we never deal with zeros or negative values.

Approaches

Brute Force Approach

A straightforward solution is to examine every possible subarray.

For each starting index, we expand the subarray one element at a time while tracking the minimum value inside the current window. For every subarray length k, we check whether:

$$\text{minimum} > \frac{\text{threshold}}{k}$$

If true, we return k.

This approach is correct because it explicitly checks every possible subarray. However, there are O(n^2) subarrays, and even with efficient minimum tracking, the total runtime becomes too large for n = 100000.

Key Insight

The critical observation is that each element can act as the minimum value of some maximal subarray.

Suppose nums[i] = x.

If we can determine the largest contiguous range where every value is at least x, then inside that range, x is the minimum element. If the range length is k, then the subarray is valid if:

$$x > \frac{\text{threshold}}{k}$$

So instead of checking all subarrays, we process each element once and determine:

• How far it can extend to the left before encountering a smaller element
• How far it can extend to the right before encountering a smaller element

This is exactly the classic "largest rectangle in histogram" pattern, which is efficiently solved using a monotonic increasing stack.

For every index:

• Find the previous smaller element
• Find the next smaller element
• Compute the width of the valid range
• Check whether the element satisfies the threshold condition for that width

This reduces the runtime to linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every subarray explicitly
Optimal Monotonic Stack	O(n)	O(n)	Finds maximal valid range for each element

Algorithm Walkthrough

Optimal Monotonic Stack Algorithm

1. Create an empty monotonic increasing stack.

The stack will store indices of elements in increasing order of values. This allows us to efficiently determine the previous smaller and next smaller elements for every position. 2. Iterate through the array from left to right.

We process each element as a candidate minimum value for some subarray. 3. While the current value is smaller than the value at the top of the stack, pop from the stack.

When an element is popped, we have discovered its next smaller element. The current index acts as the right boundary for that popped element. 4. Compute the maximal width for the popped element.

Suppose index mid is popped.

• The current index i is the first smaller element to the right
• The new top of the stack is the previous smaller element to the left
• Therefore the maximal valid width is:

$$\text{width} = i - \text{leftBoundary} - 1$$ 5. Check whether the popped element satisfies the condition.

If:

$$nums[mid] > \frac{threshold}{width}$$

then return width. 6. Push the current index onto the stack.

This maintains the monotonic increasing property. 7. After finishing the array, continue popping remaining elements.

For these elements, the right boundary becomes n. 8. If no valid subarray is found, return -1.

Why it works

For every element, the algorithm computes the largest contiguous region where that element is the minimum value. Any smaller subarray inside that region would only reduce the length and make the condition harder to satisfy. Therefore, checking the maximal possible width for each element is sufficient.

The monotonic stack guarantees that we correctly identify the nearest smaller element on both sides in linear time.

Python Solution

from typing import List

class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        stack = []

        for i in range(n + 1):
            current = nums[i] if i < n else 0

            while stack and nums[stack[-1]] > current:
                mid = stack.pop()

                left_smaller = stack[-1] if stack else -1
                width = i - left_smaller - 1

                if nums[mid] > threshold / width:
                    return width

            stack.append(i)

        return -1

The implementation uses a monotonic increasing stack of indices.

The loop runs from 0 through n. The extra iteration at n uses a sentinel value 0, which forces all remaining elements to be popped and processed.

Whenever we pop an index from the stack, we immediately know:

• Its next smaller element is the current index
• Its previous smaller element is the new top of the stack

Using these two boundaries, we compute the largest subarray where the popped element is the minimum.

We then test whether this width satisfies the threshold condition. If yes, we return immediately because the problem allows returning any valid size.

If no valid subarray exists after processing all elements, we return -1.

Go Solution

func validSubarraySize(nums []int, threshold int) int {
	n := len(nums)
	stack := []int{}

	for i := 0; i <= n; i++ {
		current := 0
		if i < n {
			current = nums[i]
		}

		for len(stack) > 0 && nums[stack[len(stack)-1]] > current {
			mid := stack[len(stack)-1]
			stack = stack[:len(stack)-1]

			leftSmaller := -1
			if len(stack) > 0 {
				leftSmaller = stack[len(stack)-1]
			}

			width := i - leftSmaller - 1

			if nums[mid] > threshold/width {
				return width
			}
		}

		stack = append(stack, i)
	}

	return -1
}

The Go implementation follows the same logic as the Python version.

A slice is used as the stack. The sentinel iteration is handled by assigning current = 0 when i == n.

Integer division in Go truncates automatically, which matches the intended comparison. Since all values fit within standard integer ranges for LeetCode constraints, no overflow issues arise.

Worked Examples

Example 1

nums = [1,3,4,3,1]
threshold = 6

We process the array using the monotonic stack.

Step	Index	Value	Stack	Action
1	0	1	[0]	Push
2	1	3	[0,1]	Push
3	2	4	[0,1,2]	Push
4	3	3	[0,1]	Pop 4
				Width = 1
				4 > 6/1, true but width 1 valid
5	3	3	[0,1,3]	Push
6	4	1	[0]	Pop 3
				Width = 3
				3 > 6/3 = 2
				Return 3

The valid subarray is [3,4,3].

Example 2

nums = [6,5,6,5,8]
threshold = 7

Step	Index	Value	Stack	Action
1	0	6	[0]	Push
2	1	5	[]	Pop 6
				Width = 1
				6 > 7/1 is false
3	1	5	[1]	Push
4	2	6	[1,2]	Push
5	3	5	[1]	Pop 6
				Width = 1
6	4	8	[1,3,4]	Push
7	5	0	[1,3]	Pop 8
				Width = 1
				8 > 7
				Return 1

The algorithm returns 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every index is pushed and popped at most once
Space	O(n)	Stack may hold all indices in worst case

The algorithm is linear because each element participates in at most one push and one pop operation. Even though the inner while loop exists, the total number of stack operations across the entire algorithm is bounded by 2n.

The space complexity is linear because the stack may contain all indices when the array is strictly increasing.

Test Cases

from typing import List

class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        stack = []

        for i in range(n + 1):
            current = nums[i] if i < n else 0

            while stack and nums[stack[-1]] > current:
                mid = stack.pop()

                left_smaller = stack[-1] if stack else -1
                width = i - left_smaller - 1

                if nums[mid] > threshold / width:
                    return width

            stack.append(i)

        return -1

sol = Solution()

assert sol.validSubarraySize([1,3,4,3,1], 6) == 3  # example 1

assert sol.validSubarraySize([6,5,6,5,8], 7) in [1,2,3,4,5]  # example 2

assert sol.validSubarraySize([1,1,1,1], 10) == -1  # no valid subarray

assert sol.validSubarraySize([10], 5) == 1  # single valid element

assert sol.validSubarraySize([5], 10) == -1  # single invalid element

assert sol.validSubarraySize([2,2,2,2], 3) == 2  # repeated values

assert sol.validSubarraySize([1000000000], 1) == 1  # very large value

assert sol.validSubarraySize([1,2,3,4,5], 9) in [3,4,5]  # increasing array

assert sol.validSubarraySize([5,4,3,2,1], 6) in [2,3]  # decreasing array

assert sol.validSubarraySize([5,5,5,5,5], 20) == 5  # whole array valid

Test Summary

Test	Why
[1,3,4,3,1], 6	Validates standard example
[6,5,6,5,8], 7	Validates multiple possible answers
[1,1,1,1], 10	Ensures algorithm returns -1 correctly
[10], 5	Tests single-element valid case
[5], 10	Tests single-element invalid case
[2,2,2,2], 3	Tests repeated equal values
[1000000000], 1	Tests large integer handling
[1,2,3,4,5], 9	Tests increasing sequence
[5,4,3,2,1], 6	Tests decreasing sequence
[5,5,5,5,5], 20	Tests full-array validity

Edge Cases

One important edge case is when no valid subarray exists. For example, nums = [1,1,1] and threshold = 100. A naive implementation might accidentally return a width due to integer division mistakes or incorrect comparisons. The monotonic stack solution correctly checks every candidate width and ultimately returns -1.

Another important case is a single-element valid subarray. For example, nums = [8] and threshold = 7. Since the subarray length is 1, the condition becomes 8 > 7. The algorithm naturally handles this because a width of 1 is computed when the element is popped from the stack.

Repeated values are also tricky. Consider nums = [5,5,5,5]. Incorrect handling of equality inside the monotonic stack can produce wrong boundaries. This implementation uses a strictly greater comparison during popping, which correctly preserves equal values and computes maximal widths accurately.

Strictly increasing arrays form another subtle scenario. In such arrays, elements remain on the stack until the sentinel iteration at the end. Without the extra sentinel pass, many candidate subarrays would never be evaluated. The implementation solves this by iterating one extra step with a synthetic value 0.

Finally, very large integer values can expose overflow bugs in some languages. The implementation avoids multiplication such as nums[mid] * width, which could overflow in other environments. Instead, it compares using division:

$$nums[mid] > threshold / width$$

This remains safe within the problem constraints.