2334. Subarray With Elements Greater Than Varying Threshold

HardStackUnion FindArrayMonotonic Stack
Leetcode Link

Problem Description

The goal is to search within an array of integers (nums) for a contiguous subsequence (a subarray) of length k, such that every element within this subarray is greater than a certain threshold divided by k. You must determine k such that this condition holds true for the subarray. If no such subarray exists, the function should return -1.

Intuition

The solution utilizes a classic problem-solving technique known as 'monotonic stack' to find the maximum k for which the threshold condition is satisfied. This approach is useful for problems involving the next greater or smaller elements in an array.

Here's the approach broken down:

  1. We use two monotonic stacks to keep track of the indices of elements in the nums array, which represent the boundaries of potential subarrays. Specifically, we identify the next smaller element to the right (right) and to the left (left) for every element in nums. This helps us determine possible values of k for each element as the potential maximum value for a subarray.

  2. We initially fill the left array with -1 and the right array with n (length of nums), since if there's no smaller element found for a particular index, the boundaries are considered to be the start and end of the nums array.

  3. We traverse the nums array twice, once from the start to the end and then from the end to the start, to populate the left and right arrays using the monotonic stacks. Whenever we find a smaller element, we update the left or right indices. This way, each element will have its left and right boundaries where a smaller element exists.

  4. After determining the left and right boundaries, we iterate through the nums array and calculate k for each element as right[i] - left[i] - 1, which defines the length of the maximum subarray where nums[i] is the smallest number.

  5. For each element, we check if nums[i] is greater than threshold / k. If it is, we have found our subarray of size k, which fits the condition, and we return that k.

  6. If we go through the entire nums array and find no such element that fits the condition for any subarray, we return -1 to indicate no subarray meets the criteria.

This approach is efficient since it traverses the array a constant number of times, giving us a linear time complexity, which is reasonable for such problems.

Learn more about Stack, Union Find and Monotonic Stack patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which algorithm should you use to find a node that is close to the root of the tree?

Solution Approach

The implementation of the solution follows these main steps:

  1. Initialize Boundary Arrays: Two arrays left and right are initialized to keep track of the smaller elements to the left and to the right of each element in nums. They are initially filled with -1 (indicating no smaller element to the left) and n (length of nums, indicating no smaller element to the right), respectively.

  2. Fill left Array with Monotonic Stack:

    • A stack stk is used to iterate over the array from left to right.
    • For each element i, the stack is used to find the most recent smaller element. As long as the top of the stack has an element greater than or equal to nums[i], it's popped out.
    • If the stack is not empty after popping, it means the current top of the stack is the index of the nearest smaller element to the left of i. This index is stored in left[i].
    • The index i is then pushed onto the stack.

  3. Fill right Array with Monotonic Stack:

    • The stack stk is reused for the reverse iteration, from right to left.
    • A similar process is followed as for the left array. Now, the stack helps in finding the nearest smaller element to the right.
    • This time, when a smaller element is found, the right array is updated with the index of this nearest smaller element to the right of i.
    • Indices are again stored in the stack during the traversal.

  4. Iterate to Find the Result:

    • We iterate through nums using the index i.
    • For each element, we compute k using right[i] - left[i] - 1. This k represents the maximum length of the subarray where the current nums[i] would be the smallest element.
    • We then check if this nums[i] is greater than threshold / k. If it is, we've found a valid k and return it.

  5. Return -1 if No Subarray Matches:

    • If no such element is found that satisfies the condition for any subarray, -1 is returned after the iteration.

The critical part of this solution is the use of the monotonic stack, which allows us to keep track of the elements in a way that we can access the nearest smaller elements in O(n) time. This stack maintains a sorted order such that for any new element, it's easy to find and record predecessors strictly decreasing in value.

In summary, a combination of monotonic stacks for efficient lookup of boundaries and a linear scan through the array allows us to calculate the size of the required subarray efficiently.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?

Example Walkthrough

Let us take a smaller example to illustrate the solution approach:

Given:

  • An array nums = [3, 1, 5, 4, 2]
  • A threshold T = 8

We're looking for the largest k such that there exists a subarray of length k where all elements are greater than T/k.

First, we initialize the left and right arrays:

1left =  [-1, -1, -1, -1, -1]
2right = [ 5,  5,  5,  5,  5] (5 is the length of `nums`)

Now letโ€™s fill the left array using the monotonic stack:

  • Start with an empty stack stk and iterate through nums from index 0 to 4.
  • For i = 0 (nums[i] = 3), the stk is empty, so left[0] remains -1. Push i to stk.
  • For i = 1 (nums[i] = 1), pop 0 from stk since nums[0] >= nums[1], and push i to stk. So left[1] remains -1.
  • Continue the iteration, and the stk will help in finding the nearest smaller element for each index.
1left = [-1, -1,  1,  2,  3]
2stk = []

Next, let's fill the right array:

  • Reuse the stk and iterate through nums reversely, from index 4 to 0.
  • For i = 4 (nums[i] = 2), the stk is empty, so right[4] remains 5. Push i to stk.
  • For i = 3 (nums[i] = 4), pop 4 from stk since nums[4] < nums[3], and set right[3] = 4. Push 3 to stk.
  • Complete the iteration similarly for the rest of the elements.
1right = [5,  5,  3,  4,  5]
2stk = []

Now find the result:

  • Iterate through nums and for each i, calculate k = right[i] - left[i] - 1 and check if nums[i] is greater than T/k.
  • For i = 0, k = right[0] - left[0] - 1 = 5 - (-1) - 1 = 5, we check if 3 > 8/5 which is not true.
  • For i = 1, k = right[1] - left[1] - 1 = 5 - (-1) - 1 = 5, again 1 > 8/5 is not true.
  • For i = 2, k = right[2] - left[2] - 1 = 3 - 1 - 1 = 1, check if 5 > 8 which is not true.
  • For i = 3, k = right[3] - left[3] - 1 = 4 - 2 - 1 = 1, check if 4 > 8 which is not true.
  • For i = 4, since nums[i] is the last element and it doesn't form a subarray, we do not need to check it.

Since there was no i for which nums[i] was greater than T/k, we return -1.

Therefore, according to this approach and the example provided, the function should return -1 as no subarray meeting the requirements can be found.

Solution Implementation

1from typing import List
2
3class Solution:
4    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
5        # Find the length of the array
6        n = len(nums)
7      
8        # Initialize arrays to keep track of the closest smaller element's index to the left and right
9        left_smaller_indices = [-1] * n
10        right_smaller_indices = [n] * n
11      
12        # Initialize an empty list to use as a stack
13        stack = []
14
15        # Forward pass to find the left smaller elements for each index
16        for i, value in enumerate(nums):
17            # Remove from stack all elements larger than or equal to current
18            while stack and nums[stack[-1]] >= value:
19                stack.pop()
20            # If stack is not empty, update left smaller index for current element
21            if stack:
22                left_smaller_indices[i] = stack[-1]
23            # Add current index to stack
24            stack.append(i)
25
26        # Clear stack to reuse it for the backward pass
27        stack.clear()
28
29        # Backward pass to find the right smaller elements for each index
30        for i in range(n - 1, -1, -1):
31            # Remove from stack all elements larger than or equal to the current
32            while stack and nums[stack[-1]] >= nums[i]:
33                stack.pop()
34            # If stack is not empty, update right smaller index for current element
35            if stack:
36                right_smaller_indices[i] = stack[-1]
37            # Add current index to stack
38            stack.append(i)
39
40        # Iterate over the array elements to find the valid subarray
41        for i, value in enumerate(nums):
42            # Calculate the length of the subarray where the current element is the minimum
43            k = right_smaller_indices[i] - left_smaller_indices[i] - 1
44            # Check if this element's value is greater than the threshold divided by the subarray size
45            if value > threshold // k:
46                # If so, this is a valid subarray size, return it
47                return k
48
49        # If no valid subarray is found, return -1.
50        return -1
51
1class Solution {
2    public int validSubarraySize(int[] nums, int threshold) {
3        int n = nums.length;
4        // Array to store the first smaller element index to the left
5        int[] leftSmallerIndex = new int[n];
6        // Array to store the first smaller element index to the right
7        int[] rightSmallerIndex = new int[n];
8      
9        // Initialize leftSmallerIndex with -1 (which means no smaller element to the left)
10        Arrays.fill(leftSmallerIndex, -1);
11        // Initialize rightSmallerIndex with n (which means no smaller element to the right)
12        Arrays.fill(rightSmallerIndex, n);
13      
14        // Stack to keep track of indices while traversing for the smaller elements
15        Deque<Integer> stack = new ArrayDeque<>();
16      
17        // Find first smaller element to the left for every element
18        for (int i = 0; i < n; ++i) {
19            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
20                stack.pop();
21            }
22            if (!stack.isEmpty()) {
23                leftSmallerIndex[i] = stack.peek();
24            }
25            stack.push(i);
26        }
27        // Clear stack for the next traversal
28        stack.clear();
29      
30        // Find first smaller element to the right for every element
31        for (int i = n - 1; i >= 0; --i) {
32            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
33                stack.pop();
34            }
35            if (!stack.isEmpty()) {
36                rightSmallerIndex[i] = stack.peek();
37            }
38            stack.push(i);
39        }
40      
41        // Check each element to see if it can be the maximum of a subarray that satisfies the condition
42        for (int i = 0; i < n; ++i) {
43            // Length of the largest subarray in which nums[i] is the smallest
44            int lengthOfSubarray = rightSmallerIndex[i] - leftSmallerIndex[i] - 1;
45            // If the current element satisfies the condition
46            // (i.e., it's greater than threshold divided by the subarray length),
47            // return the length of the subarray
48            if (nums[i] > threshold / lengthOfSubarray) {
49                return lengthOfSubarray;
50            }
51        }
52        // If no valid subarray size is found, return -1
53        return -1;
54    }
55}
56
1class Solution {
2public:
3    int validSubarraySize(vector<int>& nums, int threshold) {
4        int size = nums.size();
5
6        // Vectors to store the indexes of the next smaller element on the left and right
7        vector<int> nextSmallerLeft(size, -1);
8        vector<int> nextSmallerRight(size, size);
9
10        // Stack to keep track of indices for the monotonic property
11        stack<int> indexStack;
12
13        // Populate nextSmallerLeft
14        for (int i = 0; i < size; ++i) {
15            int currentValue = nums[i];
16            // Pop elements from stack while current value is smaller or equal
17            while (!indexStack.empty() && nums[indexStack.top()] >= currentValue) {
18                indexStack.pop();
19            }
20            // If stack is not empty then the top element is the previous smaller element
21            if (!indexStack.empty()) {
22                nextSmallerLeft[i] = indexStack.top();
23            }
24            // Push current index onto the stack
25            indexStack.push(i);
26        }
27
28        // Clear the stack to reuse for populating nextSmallerRight
29        indexStack = stack<int>();
30
31        // Populate nextSmallerRight
32        for (int i = size - 1; i >= 0; --i) {
33            int currentValue = nums[i];
34            // Pop elements from stack while the current value is smaller or equal
35            while (!indexStack.empty() && nums[indexStack.top()] >= currentValue) {
36                indexStack.pop();
37            }
38            // If stack is not empty then the top element is the next smaller element
39            if (!indexStack.empty()) {
40                nextSmallerRight[i] = indexStack.top();
41            }
42            // Push current index onto the stack
43            indexStack.push(i);
44        }
45
46        // Check for each element if it satisfies the condition
47        for (int i = 0; i < size; ++i) {
48            int currentValue = nums[i];
49            // Calculate the length of valid subarray where current element is maximum
50            int lengthOfSubarray = nextSmallerRight[i] - nextSmallerLeft[i] - 1;
51            // Check if the current element divided by the length of the subarray is
52            // greater than the threshold. If it is, return the length
53            if (currentValue > threshold / lengthOfSubarray) {
54                return lengthOfSubarray;
55            }
56        }
57
58        // If no valid subarray is found, return -1
59        return -1;
60    }
61};
62
1function validSubarraySize(nums: number[], threshold: number): number {
2    let size = nums.length;
3
4    // Arrays to store the indexes of the next smaller element on the left and right
5    let nextSmallerLeft: number[] = new Array(size).fill(-1);
6    let nextSmallerRight: number[] = new Array(size).fill(size);
7
8    // Stack to keep track of indices for the monotonic property
9    let indexStack: number[] = [];
10
11    // Populate nextSmallerLeft
12    for (let i = 0; i < size; ++i) {
13        let currentValue = nums[i];
14        // Pop elements from stack while current value is smaller or equal
15        while (indexStack.length !== 0 && nums[indexStack[indexStack.length - 1]] >= currentValue) {
16            indexStack.pop();
17        }
18        // If stack is not empty then the top element is the previous smaller element
19        if (indexStack.length !== 0) {
20            nextSmallerLeft[i] = indexStack[indexStack.length - 1];
21        }
22        // Push current index onto the stack
23        indexStack.push(i);
24    }
25
26    // Clear the stack to reuse for populating nextSmallerRight
27    indexStack = [];
28
29    // Populate nextSmallerRight
30    for (let i = size - 1; i >= 0; --i) {
31        let currentValue = nums[i];
32        // Pop elements from stack while current value is smaller or equal
33        while (indexStack.length !== 0 && nums[indexStack[indexStack.length - 1]] >= currentValue) {
34            indexStack.pop();
35        }
36        // If stack is not empty then the top element is the next smaller element
37        if (indexStack.length !== 0) {
38            nextSmallerRight[i] = indexStack[indexStack.length - 1];
39        }
40        // Push current index onto the stack
41        indexStack.push(i);
42    }
43
44    // Check for each element if it satisfies the condition
45    for (let i = 0; i < size; ++i) {
46        let currentValue = nums[i];
47        // Calculate the length of the valid subarray where the current element is the maximum
48        let lengthOfSubarray = nextSmallerRight[i] - nextSmallerLeft[i] - 1;
49        // Check if the current element divided by the length of the subarray is
50        // greater than the threshold. If it is, return the length
51        if (currentValue > threshold / lengthOfSubarray) {
52            return lengthOfSubarray;
53        }
54    }
55
56    // If no valid subarray is found, return -1
57    return -1;
58}
59
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which data structure is used to implement priority queue?

Time and Space Complexity

Time Complexity

The provided code consists of two major for-loops that iterate over the list nums. Both for-loops iterate through each element of the list once from different directions (left-to-right and right-to-left).

The first loop processes each element to find the "left" limit for each number in nums, while the second loop finds the "right" limit. Even though the loops contain while-loops that might suggest a nested loop complexity, the while-loops are only popping elements from the stack that were previously added in the same iteration. Each element is pushed and popped from the stack at most once, which means that the internal while-loops do not increase the asymptotic complexity; instead, they operate in an amortized O(1) time per loop iteration.

After setting the left and right limits, a third loop iterates over each element to calculate k and check if the value meets the condition to determine the valid subarray size.

The complexity of these operations, considering the amortized analysis for the while-loops, is O(n) for each of the three loops, leading to an overall time complexity of O(n).

Space Complexity

The space complexity is determined by the additional memory used by the algorithm aside from the input. Here, we have several data structures to consider:

  1. left list, which holds the left boundaries for each element: O(n)
  2. right list, which holds the right boundaries for each element: O(n)
  3. stk stack, which is at most the size of the list nums at any time: O(n)

Combining these, the total space complexity is O(n). There is no additional memory usage that grows with the size of the input aside from these data structures. Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Monotonic Stack/Queue Intro

Monotonic Stack Deque Intro If you'd prefer a video iframe width 560 height 315 src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe The word monotonic means a list or a

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ