Subarray With Elements Greater Than Varying Threshold — LeetCode 2334 Python Solution
HardStackUnion FindArrayMonotonic Stack
- Problem
- #2334
- Pattern
- Union-Find
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
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
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.