Welcome to Subscribe On Youtube
2334. Subarray With Elements Greater Than Varying Threshold
Description
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 <= 1051 <= nums[i], threshold <= 109
Solutions
Solution 1: Sorting
Consider traversing each element $v$ in the array $nums$ from large to small, and use a union-find structure to maintain the connected block with $v$ as the minimum value of the subarray.
During the traversal process:
The subscript of $v$ in the array $nums$ is $i$. If the element corresponding to the subscript $i-1$ has been traversed, $i-1$ and $i$ can be merged. Similarly, if the element corresponding to the subscript $i+1$ has also been traversed, the $i$ merged with $i+1$. The size of connected blocks is updated during the merge process.
$v$ is the minimum value of the current connected block, and the size of the current connected block is $size[find(i)]$. If $v>\frac{\textit{threshold}}{size[find(i)]}$, it means that a subarray that meets the conditions is found, and $true$ is returned.
Otherwise, the traversal ends and $-1$ is returned.
Time complexity $O(nlogn)$.
Similar topics:
Solution 2
Using the monotonic stack, get the left and right boundaries $left[i]$ (the position of the first element on the left that is smaller than $nums[i]$) and $right[i]$ (the position of the first element on the right that is smaller than $nums[i]$) with the current element $nums[i]$ as the minimum element.
Then for the current element $nums[i]$, there is $k=right[i]-left[i]-1$. If $nums[i]>\frac{\textit{threshold}}{k}$, it means that a subarray that meets the conditions is found and $true$ is returned.
Otherwise, the traversal ends and $-1$ is returned.
Time complexity $O(n)$.
-
class Solution { private int[] p; private int[] size; public int validSubarraySize(int[] nums, int threshold) { int n = nums.length; p = new int[n]; size = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; size[i] = 1; } int[][] arr = new int[n][2]; for (int i = 0; i < n; ++i) { arr[i][0] = nums[i]; arr[i][1] = i; } Arrays.sort(arr, (a, b) -> b[0] - a[0]); boolean[] vis = new boolean[n]; for (int[] e : arr) { int v = e[0], i = e[1]; if (i > 0 && vis[i - 1]) { merge(i, i - 1); } if (i < n - 1 && vis[i + 1]) { merge(i, i + 1); } if (v > threshold / size[find(i)]) { return size[find(i)]; } vis[i] = true; } return -1; } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } private void merge(int a, int b) { int pa = find(a), pb = find(b); if (pa == pb) { return; } p[pa] = pb; size[pb] += size[pa]; } } // Solution 2 class Solution { public int validSubarraySize(int[] nums, int threshold) { int n = nums.length; int[] left = new int[n]; int[] right = new int[n]; Arrays.fill(left, -1); Arrays.fill(right, n); Deque<Integer> stk = new ArrayDeque<>(); for (int i = 0; i < n; ++i) { int v = nums[i]; while (!stk.isEmpty() && nums[stk.peek()] >= v) { stk.pop(); } if (!stk.isEmpty()) { left[i] = stk.peek(); } stk.push(i); } stk.clear(); for (int i = n - 1; i >= 0; --i) { int v = nums[i]; while (!stk.isEmpty() && nums[stk.peek()] >= v) { stk.pop(); } if (!stk.isEmpty()) { right[i] = stk.peek(); } stk.push(i); } for (int i = 0; i < n; ++i) { int v = nums[i]; int k = right[i] - left[i] - 1; if (v > threshold / k) { return k; } } return -1; } } -
using 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]; } }; // Solution 2 class Solution { public: int validSubarraySize(vector<int>& nums, int threshold) { int n = nums.size(); vector<int> left(n, -1); vector<int> right(n, n); stack<int> stk; for (int i = 0; i < n; ++i) { int v = nums[i]; while (!stk.empty() && nums[stk.top()] >= v) stk.pop(); if (!stk.empty()) left[i] = stk.top(); stk.push(i); } stk = stack<int>(); for (int i = n - 1; ~i; --i) { int v = nums[i]; while (!stk.empty() && nums[stk.top()] >= v) stk.pop(); if (!stk.empty()) right[i] = stk.top(); stk.push(i); } for (int i = 0; i < n; ++i) { int v = nums[i]; int k = right[i] - left[i] - 1; if (v > threshold / k) return k; } return -1; } }; -
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 -1 # Solution 2 class Solution: def validSubarraySize(self, nums: List[int], threshold: int) -> int: n = len(nums) left = [-1] * n right = [n] * n stk = [] for i, v in enumerate(nums): while stk and nums[stk[-1]] >= v: stk.pop() if stk: left[i] = stk[-1] stk.append(i) stk = [] for i in range(n - 1, -1, -1): while stk and nums[stk[-1]] >= nums[i]: stk.pop() if stk: right[i] = stk[-1] stk.append(i) for i, v in enumerate(nums): k = right[i] - left[i] - 1 if v > threshold // k: return k return -1 -
func validSubarraySize(nums []int, threshold int) int { n := len(nums) p := make([]int, n) size := make([]int, n) for i := range p { p[i] = i size[i] = 1 } var find func(int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } merge := func(a, b int) { pa, pb := find(a), find(b) if pa == pb { return } p[pa] = pb size[pb] += size[pa] } arr := make([][]int, n) for i, v := range nums { arr[i] = []int{v, i} } sort.Slice(arr, func(i, j int) bool { return arr[i][0] > arr[j][0] }) vis := make([]bool, n) for _, e := range arr { v, i := e[0], e[1] if i > 0 && vis[i-1] { merge(i, i-1) } if i < n-1 && vis[i+1] { merge(i, i+1) } if v > threshold/size[find(i)] { return size[find(i)] } vis[i] = true } return -1 } // Solution 2 func validSubarraySize(nums []int, threshold int) int { n := len(nums) left := make([]int, n) right := make([]int, n) for i := range left { left[i] = -1 right[i] = n } var stk []int for i, v := range nums { for len(stk) > 0 && nums[stk[len(stk)-1]] >= v { stk = stk[:len(stk)-1] } if len(stk) > 0 { left[i] = stk[len(stk)-1] } stk = append(stk, i) } stk = []int{} for i := n - 1; i >= 0; i-- { v := nums[i] for len(stk) > 0 && nums[stk[len(stk)-1]] >= v { stk = stk[:len(stk)-1] } if len(stk) > 0 { right[i] = stk[len(stk)-1] } stk = append(stk, i) } for i, v := range nums { k := right[i] - left[i] - 1 if v > threshold/k { return k } } return -1 }