HardNo. 2334
Subarray With Elements Greater Than Varying Threshold — LeetCode 2334 Python Solution
- Pattern
- Union-Find
- Topics
- Stack, Union Find, Array, Monotonic Stack
- Reading time
- 5 min
- Source
- leetcode.com
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.
Example
- 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.
Python solution
class Solution:
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 -1Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2334. Subarray With Elements Greater Than Varying Threshold is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0084 | Largest Rectangle in Histogram | Hard |
| 0456 | 132 Pattern | Medium |
| 0503 | Next Greater Element II | Medium |
| 0654 | Maximum Binary Tree | Medium |
| 0739 | Daily Temperatures | Medium |
| 0853 | Car Fleet | Medium |
Frequently asked questions
- How hard is LeetCode 2334. Subarray With Elements Greater Than Varying Threshold?
LeetCode 2334. Subarray With Elements Greater Than Varying Threshold is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2334. Subarray With Elements Greater Than Varying Threshold?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2334. Subarray With Elements Greater Than Varying Threshold?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2334. Subarray With Elements Greater Than Varying Threshold cover?
LeetCode 2334. Subarray With Elements Greater Than Varying Threshold is tagged Stack, Union Find, Array and Monotonic Stack on LeetCode.