Subarray With Elements Greater Than Varying Threshold

Hard

#2126Time: O(n^2), where n is the number of elements in `nums`. The nested loops result in a quadratic number of checks.Space: O(1) extra space, as we only use a few variables to store the loop indices and the running minimum.1 company

Algorithms

Union Find

Data structures

Array Stack Monotonic Stack

Companies

instabase

Prompt

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⁹

Approaches

3 approaches with complexity analysis and trade-offs.

This approach systematically checks every possible contiguous subarray within the nums array. For each subarray, it finds the minimum element and the length, then verifies if the given condition min(subarray) > threshold / length is satisfied. It's the most straightforward, brute-force method.

Algorithm

Use two nested loops to iterate through all possible subarrays. The outer loop with index i determines the start of the subarray, and the inner loop with index j determines the end.
For each subarray nums[i...j], we need to find its minimum element minVal and its length k = j - i + 1.
To avoid a third loop which would result in an O(n^3) solution, we can maintain the minimum value as we extend the subarray (i.e., as j increases for a fixed i).
For each subarray, check if the condition minVal > threshold / k is met. To avoid floating-point arithmetic and potential precision issues, it's better to check the equivalent condition (long)minVal * k > threshold.
If the condition holds, we have found a valid subarray of length k, and we can immediately return k.
If the loops complete without finding any such subarray, it means no solution exists, so we return -1.

Walkthrough

The brute-force approach iterates through all possible starting and ending points of a subarray. For each subarray, it calculates its length and finds its minimum element, then checks if the condition is satisfied.

An initial naive implementation would use three nested loops: two for the subarray boundaries and one to find the minimum, leading to O(n³) complexity. We can optimize this by observing that as we extend a subarray nums[i...j] to nums[i...j+1], the new minimum is just the minimum of the old subarray's minimum and the new element nums[j+1]. This optimization reduces the complexity to O(n²).

Here is the algorithm for the optimized brute-force approach:

Iterate through each possible starting index i from 0 to n-1.
For each i, initialize minVal = nums[i].
Start an inner loop for the ending index j from i to n-1.
In the inner loop, update minVal = Math.min(minVal, nums[j]).
Calculate the length of the current subarray: k = j - i + 1.
Check if (long)minVal * k > threshold. This is a more robust way to check minVal > threshold / k.
If the condition is true, a valid subarray has been found. Return its length k.
If the loops finish without returning, no valid subarray exists. Return -1.

1class Solution {2    public int validSubarraySize(int[] nums, int threshold) {3        int n = nums.length;4        for (int i = 0; i < n; i++) {5            int minVal = nums[i];6            for (int j = i; j < n; j++) {7                minVal = Math.min(minVal, nums[j]);8                int k = j - i + 1;9                if ((long) minVal * k > threshold) {10                    return k;11                }12            }13        }14        return -1;15    }16}

Complexity

Time

O(n^2), where n is the number of elements in `nums`. The nested loops result in a quadratic number of checks.

Space

O(1) extra space, as we only use a few variables to store the loop indices and the running minimum.

Trade-offs

Pros

Simple to understand and implement.
Requires no extra space, making it very memory-efficient.

Cons

The O(n^2) time complexity is too slow for the given constraints (n up to 10^5) and will result in a Time Limit Exceeded (TLE) error on most platforms.

This approach cleverly reframes the problem by iterating through the numbers from largest to smallest. It uses a Disjoint Set Union (DSU) data structure to efficiently track and merge contiguous segments of numbers that are all above a certain value. For each number, it checks if the segment it belongs to can form a valid subarray.

Algorithm

The core idea is to process elements in descending order of their values. For each value v, we consider it as the potential minimum of a subarray.
Create pairs of (value, index) and sort them in descending order of value.
Initialize a Disjoint Set Union (DSU) data structure to manage contiguous segments of processed elements. Each index starts in its own set of size 1.
Iterate through the sorted (val, idx) pairs:
- Mark the current index idx as processed (e.g., using a visited array).
- Check its neighbors (idx-1 and idx+1). If a neighbor has already been processed, merge the sets of idx and the neighbor using the DSU's union operation.
- After merging, find the size k of the new contiguous segment containing idx.
- This segment represents a subarray of length k where all elements are at least val.
- Check if (long)val * k > threshold. If true, we have found a valid subarray of length k, so we return k.
If the loop completes, no solution was found, so return -1.

Walkthrough

Instead of checking every subarray, we can iterate through each element nums[i] and consider it as the minimum element of a potential subarray. The condition to check is nums[i] > threshold / k, where k is the length of this subarray.

To do this efficiently, we process elements from largest to smallest. This ensures that when we consider an element val at index idx, any other elements we have already processed (and formed segments with) have values greater than or equal to val. A Disjoint Set Union (DSU) data structure is ideal for tracking the size of these dynamically merging contiguous segments.

Here is the detailed algorithm:

Create an array of indices 0, 1, ..., n-1.
Sort this index array based on the values in nums in descending order. This way, we process indices corresponding to larger nums values first.
Initialize a DSU structure of size n and a visited boolean array of size n.
Iterate through the sorted indices id: a. Mark visited[id] as true. b. Check the left neighbor id-1. If id > 0 and visited[id-1] is true, perform dsu.union(id, id-1). c. Check the right neighbor id+1. If id < n-1 and visited[id+1] is true, perform dsu.union(id, id+1). d. Get the size of the merged component containing id: k = dsu.getSize(id). e. Check if (long)nums[id] * k > threshold. If this holds, we've found a subarray of length k where every element is at least nums[id], satisfying the condition. Return k.
If the loop finishes, return -1.

1class Solution {2    class DSU {3        private int[] parent;4        private int[] sz;5        public DSU(int n) {6            parent = new int[n];7            sz = new int[n];8            for (int i = 0; i < n; i++) {9                parent[i] = i;10                sz[i] = 1;11            }12        }13        public int find(int i) {14            if (parent[i] == i) return i;15            return parent[i] = find(parent[i]);16        }17        public void union(int i, int j) {18            int rootI = find(i);19            int rootJ = find(j);20            if (rootI != rootJ) {21                if (sz[rootI] < sz[rootJ]) {22                    int temp = rootI;23                    rootI = rootJ;24                    rootJ = temp;25                }26                parent[rootJ] = rootI;27                sz[rootI] += sz[rootJ];28            }29        }30        public int getSize(int i) {31            return sz[find(i)];32        }33    }34 35    public int validSubarraySize(int[] nums, int threshold) {36        int n = nums.length;37        Integer[] ids = new Integer[n];38        for (int i = 0; i < n; i++) {39            ids[i] = i;40        }41        Arrays.sort(ids, (a, b) -> Integer.compare(nums[b], nums[a]));42 43        DSU dsu = new DSU(n);44        boolean[] visited = new boolean[n];45 46        for (int id : ids) {47            visited[id] = true;48            if (id > 0 && visited[id - 1]) {49                dsu.union(id, id - 1);50            }51            if (id < n - 1 && visited[id + 1]) {52                dsu.union(id, id + 1);53            }54            int k = dsu.getSize(id);55            if ((long) nums[id] * k > threshold) {56                return k;57            }58        }59        return -1;60    }61}

Complexity

Time

O(n log n), where n is the length of `nums`. The sorting step is the bottleneck. The DSU operations in the loop take O(n * α(n)), which is nearly linear.

Space

O(n) to store the DSU parent and size arrays, the sorted indices array, and the visited array.

Trade-offs

Pros

Much more efficient than the brute-force approach.
Guaranteed to find a solution if one exists.

Cons

More complex to implement compared to the brute-force approach.
The O(n log n) time complexity is not the most optimal solution.

This optimal approach uses a monotonic stack to efficiently determine, for each element nums[i], the scope of the subarray where nums[i] acts as the minimum. By finding the nearest smaller elements on both sides (prevSmaller and nextSmaller), we can calculate the length k of this subarray and check the condition nums[i] * k > threshold in linear time.

Algorithm

For each element nums[i], we find the largest possible subarray for which nums[i] is the minimum element.
The boundaries of this subarray are determined by the prevSmaller[i] (index of the first element to the left of i that is smaller than nums[i]) and nextSmaller[i] (index of the first element to the right of i that is smaller than nums[i]).
The length of this largest subarray is k = nextSmaller[i] - prevSmaller[i] - 1.
For this subarray, the condition becomes nums[i] > threshold / k. If this holds, we have found a valid subarray of length k and can return k.
The prevSmaller and nextSmaller arrays can be computed efficiently in O(n) time using a monotonic stack.
We can perform two passes to compute these arrays and a third pass to check the condition, or combine the logic into a more optimized single pass.

Walkthrough

The most efficient solution relies on a key insight: for any valid subarray, there must be a minimum element. We can iterate through each element nums[i] and treat it as the minimum of a potential candidate subarray. For a fixed minimum nums[i], the condition nums[i] > threshold / k is easiest to satisfy when k is as large as possible.

The largest subarray for which nums[i] is the minimum is bounded by the first smaller element to its left and the first smaller element to its right. We can find these boundaries for all elements in O(n) time using a monotonic stack.

Here is the algorithm:

Compute prevSmaller array: Create an array prevSmaller of size n. Iterate from i = 0 to n-1. Use a monotonically increasing stack (of indices) to find the index of the first element to the left of i that is smaller than nums[i]. If no such element exists, store -1.
Compute nextSmaller array: Similarly, create nextSmaller array. Iterate from i = n-1 to 0 and use a monotonic stack to find the index of the first element to the right of i that is smaller than nums[i]. If none exists, store n.
Check Condition: Iterate from i = 0 to n-1. For each i: a. Calculate the length of the subarray where nums[i] is the minimum: k = nextSmaller[i] - prevSmaller[i] - 1. b. If k > 0, check if (long)nums[i] * k > threshold. c. If the condition is true, we have found a valid subarray of length k. Return k.
If the loop completes, no valid subarray was found. Return -1.

1import java.util.ArrayDeque;2import java.util.Deque;3 4class Solution {5    public int validSubarraySize(int[] nums, int threshold) {6        int n = nums.length;7        int[] prevSmaller = new int[n];8        Deque<Integer> stack = new ArrayDeque<>();9 10        // Find previous smaller element for each element11        for (int i = 0; i < n; i++) {12            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {13                stack.pop();14            }15            prevSmaller[i] = stack.isEmpty() ? -1 : stack.peek();16            stack.push(i);17        }18 19        stack.clear();20        int[] nextSmaller = new int[n];21 22        // Find next smaller element for each element23        for (int i = n - 1; i >= 0; i--) {24            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {25                stack.pop();26            }27            nextSmaller[i] = stack.isEmpty() ? n : stack.peek();28            stack.push(i);29        }30 31        // Check the condition for each potential subarray32        for (int i = 0; i < n; i++) {33            int k = nextSmaller[i] - prevSmaller[i] - 1;34            if (k > 0) {35                if ((long) nums[i] * k > threshold) {36                    return k;37                }38            }39        }40 41        return -1;42    }43}

Complexity

Time

O(n). Each of the three passes (computing `prevSmaller`, `nextSmaller`, and checking the condition) takes linear time. Each element is pushed onto and popped from the stack at most once.

Space

O(n) to store the `prevSmaller` and `nextSmaller` arrays, as well as the stack used during computation.

Trade-offs

Pros

Optimal time complexity of O(n).
Provides a deterministic and efficient way to check all relevant candidate subarrays without redundant computations.

Cons

The logic can be less intuitive to grasp compared to other approaches.
Requires O(n) extra space, which might be a concern for extremely large n under strict memory constraints.

Solutions

Solution

1class Solution {2private3  int[] p;4private5  int[] size;6public7  int validSubarraySize(int[] nums, int threshold) {8    int n = nums.length;9    p = new int[n];10    size = new int[n];11    for (int i = 0; i < n; ++i) {12      p[i] = i;13      size[i] = 1;14    }15    int[][] arr = new int[n][2];16    for (int i = 0; i < n; ++i) {17      arr[i][0] = nums[i];18      arr[i][1] = i;19    }20    Arrays.sort(arr, (a, b)->b[0] - a[0]);21    boolean[] vis = new boolean[n];22    for (int[] e : arr) {23      int v = e[0], i = e[1];24      if (i > 0 && vis[i - 1]) {25        merge(i, i - 1);26      }27      if (i < n - 1 && vis[i + 1]) {28        merge(i, i + 1);29      }30      if (v > threshold / size[find(i)]) {31        return size[find(i)];32      }33      vis[i] = true;34    }35    return -1;36  }37private38  int find(int x) {39    if (p[x] != x) {40      p[x] = find(p[x]);41    }42    return p[x];43  }44private45  void merge(int a, int b) {46    int pa = find(a), pb = find(b);47    if (pa == pb) {48      return;49    }50    p[pa] = pb;51    size[pb] += size[pa];52  }53}

1using pii = pair < int , int > ; class Solution { public: vector < int > p ; vector < int > size ; int validSubarraySize ( vector < int >& nums , int threshold ) { int n = nums . size (); p . resize ( n ); for ( int i = 0 ; i < n ; ++ i ) p [ i ] = i ; size . assign ( n , 1 ); vector < pii > arr ( n ); for ( int i = 0 ; i < n ; ++ i ) arr [ i ] = { nums [ i ], i }; sort ( arr . begin (), arr . end ()); vector < bool > vis ( n ); for ( int j = n - 1 ; ~ j ; -- j ) { int v = arr [ j ]. first , i = arr [ j ]. second ; if ( i && vis [ i - 1 ]) merge ( i , i - 1 ); if ( j < n - 1 && vis [ i + 1 ]) merge ( i , i + 1 ); if ( v > threshold / size [ find ( i )]) return size [ find ( i )]; vis [ i ] = true ; } return - 1 ; } int find ( int x ) { if ( p [ x ] != x ) p [ x ] = find ( p [ x ]); return p [ x ]; } void merge ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) return ; p [ pa ] = pb ; size [ pb ] += size [ pa ]; } };

1class Solution:2    def validSubarraySize(self, nums: List[int], threshold: int) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def merge(a, b): pa, pb = find(a), find(b) if pa == pb: return p[pa] = pb size[pb] += size[pa] n = len(nums) p = list(range(n)) size = [1] * n arr = sorted(zip(nums, range(n)), reverse=True) vis = [False] * n for v, i in arr: if i and vis[i - 1]: merge(i, i - 1) if i < n - 1 and vis[i + 1]: merge(i, i + 1) if v > threshold // size[find(i)]: return size[find(i)] vis[i] = True return - 1

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  int[] p;4private5  int[] size;6public7  int validSubarraySize(int[] nums, int threshold) {8    int n = nums.length;9    p = new int[n];10    size = new int[n];11    for (int i = 0; i < n; ++i) {12      p[i] = i;13      size[i] = 1;14    }15    int[][] arr = new int[n][2];16    for (int i = 0; i < n; ++i) {17      arr[i][0] = nums[i];18      arr[i][1] = i;19    }20    Arrays.sort(arr, (a, b)->b[0] - a[0]);21    boolean[] vis = new boolean[n];22    for (int[] e : arr) {23      int v = e[0], i = e[1];24      if (i > 0 && vis[i - 1]) {25        merge(i, i - 1);26      }27      if (i < n - 1 && vis[i + 1]) {28        merge(i, i + 1);29      }30      if (v > threshold / size[find(i)]) {31        return size[find(i)];32      }33      vis[i] = true;34    }35    return -1;36  }37private38  int find(int x) {39    if (p[x] != x) {40      p[x] = find(p[x]);41    }42    return p[x];43  }44private45  void merge(int a, int b) {46    int pa = find(a), pb = find(b);47    if (pa == pb) {48      return;49    }50    p[pa] = pb;51    size[pb] += size[pa];52  }53}

1using pii = pair < int , int > ; class Solution { public: vector < int > p ; vector < int > size ; int validSubarraySize ( vector < int >& nums , int threshold ) { int n = nums . size (); p . resize ( n ); for ( int i = 0 ; i < n ; ++ i ) p [ i ] = i ; size . assign ( n , 1 ); vector < pii > arr ( n ); for ( int i = 0 ; i < n ; ++ i ) arr [ i ] = { nums [ i ], i }; sort ( arr . begin (), arr . end ()); vector < bool > vis ( n ); for ( int j = n - 1 ; ~ j ; -- j ) { int v = arr [ j ]. first , i = arr [ j ]. second ; if ( i && vis [ i - 1 ]) merge ( i , i - 1 ); if ( j < n - 1 && vis [ i + 1 ]) merge ( i , i + 1 ); if ( v > threshold / size [ find ( i )]) return size [ find ( i )]; vis [ i ] = true ; } return - 1 ; } int find ( int x ) { if ( p [ x ] != x ) p [ x ] = find ( p [ x ]); return p [ x ]; } void merge ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) return ; p [ pa ] = pb ; size [ pb ] += size [ pa ]; } };

1class Solution:2    def validSubarraySize(self, nums: List[int], threshold: int) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def merge(a, b): pa, pb = find(a), find(b) if pa == pb: return p[pa] = pb size[pb] += size[pa] n = len(nums) p = list(range(n)) size = [1] * n arr = sorted(zip(nums, range(n)), reverse=True) vis = [False] * n for v, i in arr: if i and vis[i - 1]: merge(i, i - 1) if i < n - 1 and vis[i + 1]: merge(i, i + 1) if v > threshold // size[find(i)]: return size[find(i)] vis[i] = True return - 1

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.