Skip to main content
Talentd

Subarray With Elements Greater Than Varying Threshold - Solution & Explanation

HardArrayStackUnion FindMonotonic Stack9 min readAsked at: Amazon, Google, Instabase +1
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i], threshold <= 109

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.

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.

Code

PythonC++

Python

C++

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.

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.

Code

JavaJavaScript

Java

JavaScript

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

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
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ā€”

Detailed Complexity Analysis

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

Video Solution

Biweekly Contest 82 | 2334. Subarray With Elements Greater Than Varying Threshold ā€¢ codingMohan ā€¢ 3,771 views views

Watch 6 more video solutions ā†’

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.

Ready to solve this problem?

Practice Subarray With Elements Greater Than Varying Threshold with our built-in code editor and test cases.

Practice on FleetCode
Previous

K Divisible Elements Subarrays

Next

Maximum Subarray Min-Product