[Solved] Subarray With Elements Greater Than Varying Threshold LeetCode Contest

Subarray With Elements Greater Than Varying Threshold: 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

Approach:-

• We consider the current element as the minimum element and try to find out the prev smaller and next smaller elements.
• Once we know that, we can calculate the max.
• subarray length K which will allow us to get the least threshold / k.
  Please Upvote if you like
  Time Complexity:- O(N)

class Solution {
public:
    int validSubarraySize(vector<int>& nums, int threshold) {
        int n = nums.size();
        vector<long long> lr(n, n), rl(n, -1);
        
        vector<int> s;
        for(int i = 0; i < n; ++i) {
            while(!s.empty() and nums[i] < nums[s.back()]) {
                lr[s.back()] = i;
                s.pop_back();
            }
            s.push_back(i);
        }
        s.clear();
        for(int i = n - 1; ~i; --i) {
            while(!s.empty() and nums[i] < nums[s.back()]) {
                rl[s.back()] = i;
                s.pop_back();
            }
            s.push_back(i);
        }
        
        for(int i = 0; i < n; ++i) {
            long long length = lr[i] - rl[i] - 1;
            if(1LL * nums[i] * length > threshold) return length;
        }
        
        return -1;
    }
};

def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        nums = [0] + nums + [0]
        stack = [0]
        for i in range(1,len(nums)):
            while nums[i] < nums[stack[-1]]:
                tmp = nums[stack.pop()]
                if tmp > threshold / (i - stack[-1] - 1):
                    return i - stack[-1] - 1
            stack.append(i)
        return -1

1. If the minimum value of A min(A) > threshold / len(A) then A is one of the answers.
2. If any element x <= threshold / len(A), A cannot be the answer. We call x a bad point.
3. A can be divided into segments by these bad points.

We can find those segments and recursively validate each one.

public int validSubarraySize(int[] nums, int threshold) {
        int n = nums.length;
        return dfs(nums, 0, n - 1, threshold);
    }
    
    private int dfs(int[] nums, int l, int r, int t) {
        if(l > r) {
            return -1;
        }
        if(l == r) {
            return nums[l] > t ? 1 : -1;
        }
        
        int n = r - l + 1;
        for(int i = l; i <= r; ) {
            if(nums[i] <= t / n) {
                i++;
                continue;
            }
            int j = i;
            int min = Integer.MAX_VALUE;
            while(i <= r && nums[i] > t / n) {
                min = Math.min(min, nums[i]);
                i++;
            }
            
            if(min > t / (i - j)) {
                return i - j;
            }
            
            int res = dfs(nums, j, i - 1, t);
                
            if(res != -1) {
                return res;
            }
        }
        
        return -1;
}

Happy Learning – If you require any further information, feel free to contact me.