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).

2334 - Subarray With Elements Greater Than Varying Threshold

2334. Subarray With Elements Greater Than Varying Threshold

Problem

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

2334. Subarray With Elements Greater Than Varying Threshold

Problem

Solution

All Problems

All Solutions