Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2334.html
2334. Subarray With Elements Greater Than Varying Threshold
- Difficulty: Hard.
- Related Topics: Array, Stack, Union Find, Monotonic Stack.
- Similar Questions: Maximum Subarray Min-Product, Smallest K-Length Subsequence With Occurrences of a Letter, K Divisible Elements Subarrays.
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
.
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
Solution
-
class Solution { public int validSubarraySize(int[] nums, int threshold) { int n = nums.length; int[] min = new int[n]; // base case TreeSet<Integer> dead = new TreeSet<>(Arrays.asList(n, -1)); PriorityQueue<Integer> maxheap = new PriorityQueue<>(Comparator.comparingInt(o -> -min[o])); for (int i = 0; i < n; i++) { min[i] = threshold / nums[i] + 1; if (min[i] > nums.length) { // dead, this element should never appear in the answer dead.add(i); } else { maxheap.offer(i); } } while (!maxheap.isEmpty()) { int cur = maxheap.poll(); if (dead.higher(cur) - dead.lower(cur) - 1 < min[cur]) { // widest open range < minimum required length, this index is also bad. dead.add(cur); } else { // otherwise we've found it! return min[cur]; } } return -1; } } ############ 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; } }
-
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 ############ # 2334. Subarray With Elements Greater Than Varying Threshold # https://leetcode.com/problems/subarray-with-elements-greater-than-varying-threshold class Solution: def validSubarraySize(self, nums: List[int], threshold: int) -> int: n = len(nums) prevSmaller = [-1] * n nextSmaller = [n] * n stack = [] for i, x in enumerate(nums): while stack and x < nums[stack[-1]]: nextSmaller[stack.pop()] = i stack.append(i) stack = [] for i in range(n - 1, -1,- 1): while stack and nums[i] < nums[stack[-1]]: prevSmaller[stack.pop()] = i stack.append(i) for i, x in enumerate(nums): left, right = prevSmaller[i], nextSmaller[i] N = right - left - 1 if x > threshold // N: return N return -1
-
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; } };
-
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 }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).