1063. Number of Valid Subarrays

HardStackArrayMonotonic Stack
Leetcode Link

Problem Description

The problem asks us to count the number of subarrays within a given array nums, where each subarray must adhere to the condition that its leftmost element is not larger than any of the other elements within the same subarray. A subarray is defined as a contiguous segment of an array.

Essentially, starting at any element within nums, we can form a valid subarray by extending it to the right as long as we encounter elements that are greater than or equal to this starting element. The count of all such possible subarrays is the required answer.

Intuition

To solve this problem efficiently, we can use a stack to keep track of elements and their indices. The core idea is to iterate through the array from right to left, adding elements to the stack as we go. For each element, we consider it as the potential leftmost element of a subarray and try to find out how many subarrays can be formed with this condition.

The stack will maintain the indices of elements in decreasing order leftward from the current element. The constraints of the problem ensure that for each element, any valid subarray can only extend as far as the element immediately preceding a smaller element in the array. This is because the leftmost element must be smaller than or equal to all other elements in the subarray.

During each iteration, we remove elements from the stack that are smaller than the current element because they cannot be the end of a valid subarray starting with the current element; their presence in the stack would violate our condition.

The difference in indices between the current element's index and the index of the element on top of the stack after popping (or the array's length if the stack is empty) gives us the number of valid subarrays with the current element as the leftmost item. This way, we can calculate the total number of valid subarrays efficiently without having to explicitly enumerate them.

Learn more about Stack and Monotonic Stack patterns.

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

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Solution Approach

The provided Python solution utilizes a Monotonic Stack, which is a stack where the elements are in a single non-increasing or non-decreasing order. This pattern is particularly useful for problems involving subarray intervals and next greater elements.

Here's a step-by-step explanation of the approach:

  1. Initialize Variables: We start by initializing a list called stk (which will serve as our stack), and a variable ans which will accumulate the count of valid subarrays.

  2. Iterate Through the Array: We iterate through the array nums in reverse (from the last element to the first). This is done to treat each element as the potential starting point of several subarrays.

  3. Maintain Monotonic Stack:

    • While there are elements in the stack and the element at the index specified by the top of the stack is greater than or equal to the current element nums[i], we pop elements from the stack.
    • This ensures that the stack will always be in non-decreasing order and stores indices of elements that comply with our requirement of valid subarray start points.

  4. Calculate Subarray Count for Current Element:

    • After popping all of the elements greater than the current element, the difference between the index on the top of the stack (if not empty) or the length of the array n (if the stack is empty) and the current index i gives the number of subarrays that can be formed with the current element as the leftmost one. We add this number to our ans.

  5. Push the Current Index onto the Stack: The current index i is then added to the stack since it could be the start of a valid subarray with respect to the future elements as we continue iterating backward.

  6. Return the Result: Once the iteration is complete, the total count of valid subarrays accumulated in ans is returned.

The stack is used here as a clever way to remember which elements have not yet found a smaller preceding element, and therefore from which points valid subarrays can still be extended. The stack maintenance ensures the next smaller element's index is always available for the calculations, minimizing the operations needed to get the subarray counts.

Using this approach, we can run through the array a single time with our operations on the stack being constant time on average due to the properties of a stack. This allows the algorithm to achieve a time complexity of O(n), where n is the length of the array.

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

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's say we have an example array:

1nums = [3, 1, 2, 4]

We want to count the subarrays where the leftmost element is not larger than the other elements in the subarray.

Here's how the solution approach can be applied to this example:

  1. Initialize Variables:

    • stk = [] (our stack)
    • ans = 0 (answer to accumulate subarray counts)

  2. Iterate Through the Array:

    • We will iterate from right to left, which means we'll look at the elements in the following order: 4, 2, 1, 3.

  3. Maintain Monotonic Stack:

    • When we start at index 3 (nums[3] = 4), the stack is empty so we proceed.
    • At index 2 (nums[2] = 2), the stack contains index 3 and nums[3] >= nums[2]. No popping required.
    • At index 1 (nums[1] = 1), the stack contains indices 3 and 2. nums[3] and nums[2] are both greater than nums[1], so we pop both from the stack.
    • At index 0 (nums[0] = 3), the stack is empty as both prev elements were smaller.

  4. Calculate Subarray Count for Current Element:

    • For index 3, stack is empty so n - i = 4 - 3 = 1 subarray possible which is [4].
    • For index 2, after stack operation top of stack is index 3, 3 - 2 = 1 subarray is possible which is [2, 4].
    • For index 1, stack is empty after popping, n - i = 4 - 1 = 3 subarrays possible: [1, 2, 4], [1, 2], and [1].
    • For index 0, stack is empty so n - i = 4 - 0 = 4 subarrays are possible: [3, 1, 2, 4], [3, 1, 2], [3, 1], and [3].
    • Add all the counts: ans = 1 + 1 + 3 + 4 = 9.

  5. Push the Current Index onto the Stack:

    • After processing each element, we push its index onto the stack.
    • End of index 3: stk = [3]
    • End of index 2: stk = [3, 2]
    • End of index 1: stk = [1]
    • End of index 0: stk = [0]

  6. Return the Result:

    • By the end of the iteration, ans = 9, which means there are 9 subarrays in nums where the leftmost element is not larger than the other elements.

Thus, we have found the number of subarrays that adhere to the given condition for the array [3, 1, 2, 4] using the solution approach described, with a final result of 9.

Solution Implementation

1# Import the typing module to specify the type of the List
2from typing import List
3
4class Solution:
5    def validSubarrays(self, nums: List[int]) -> int:
6        # Get the length of the input list
7        n = len(nums)
8      
9        # Initialize a stack to keep track of indices for valid subarrays
10        stack = []
11      
12        # Initialize the counter for valid subarrays
13        valid_subarray_count = 0
14      
15        # Iterate over the input list in reverse order
16        for i in range(n - 1, -1, -1):
17            # Pop elements from the stack while the current element is less than
18            # the element at the index on top of the stack, which ensures that
19            # we only count valid subarrays (non-decreasing order)
20            while stack and nums[stack[-1]] >= nums[i]:
21                stack.pop()
22          
23            # Calculate the number of valid subarrays including the current element.
24            # If the stack is not empty, subtract the current index from the index on
25            # top of the stack. If the stack is empty, it means the current element
26            # can form valid subarrays with all subsequent elements.
27            valid_subarray_count += (stack[-1] if stack else n) - i
28          
29            # Push the current index onto the stack
30            stack.append(i)
31      
32        # Return the total count of valid subarrays
33        return valid_subarray_count
34
1class Solution {
2    public int validSubarrays(int[] nums) {
3        // Get the total number of elements in the array.
4        int totalElements = nums.length;
5        // Initialize a stack that will help keep track of the indices.
6        Deque<Integer> indexStack = new ArrayDeque<>();
7        // This variable will store the count of valid subarrays.
8        int validSubarrayCount = 0;
9
10        // Iterate over the elements starting from the end of the array.
11        for (int i = totalElements - 1; i >= 0; --i) {
12            // If the stack is not empty and the last element in the stack 
13            // is greater than or equal to the current element, pop the stack.
14            while (!indexStack.isEmpty() && nums[indexStack.peek()] >= nums[i]) {
15                indexStack.pop();
16            }
17
18            // Calculate the number of valid subarrays ending with nums[i].
19            // If the stack is empty, we can form subarrays with all the following elements.
20            // If the stack is not empty, we form subarrays up to the last smaller element found.
21            validSubarrayCount += (indexStack.isEmpty() ? totalElements : indexStack.peek()) - i;
22
23            // Push the current index on to the stack.
24            indexStack.push(i);
25        }
26
27        // Return the count of valid subarrays.
28        return validSubarrayCount;
29    }
30}
31
1class Solution {
2public:
3    int validSubarrays(vector<int>& nums) {
4        int n = nums.size(); // Get the number of elements in the nums vector.
5        stack<int> indexStack; // This stack will store the indices of elements in nums.
6        int answer = 0; // This will hold the count of valid subarrays.
7
8        // Start from the end of the nums vector and move backwards.
9        for (int i = n - 1; i >= 0; --i) {
10            // Pop elements from the stack if they are greater than or equal to nums[i].
11            // We want to find the next smaller element in the remaining array.
12            while (!indexStack.empty() && nums[indexStack.top()] >= nums[i]) {
13                indexStack.pop();
14            }
15
16            // If stack is not empty, then the current valid subarray size is (index at top of stack - current index).
17            // If the stack is empty, all elements to the right are greater, hence (n - current index).
18            answer += indexStack.empty() ? n - i : indexStack.top() - i;
19          
20            // Push the current index into the stack.
21            indexStack.push(i);
22        }
23
24        // Return the final count of valid subarrays.
25        return answer;
26    }
27};
28
1function validSubarrays(nums: number[]): number {
2    const arrayLength = nums.length; // Total number of elements in the input array.
3    const stack: number[] = []; // Stack to hold indices of elements.
4    let countValidSubarrays = 0; // Stores the count of valid subarrays.
5
6    // Iterate over the array in reverse.
7    for (let index = arrayLength - 1; index >= 0; --index) {
8        // Pop elements from the stack while the current element is less than
9        // the element corresponding to the top index in the stack.
10        while (stack.length && nums[stack[stack.length - 1]] >= nums[index]) {
11            stack.pop();
12        }
13
14        // Increment the count of valid subarrays by the difference of
15        // top stack index (representing the next greater element's index) and current index.
16        // If stack is empty, use arrayLength as all elements to the right are valid.
17        countValidSubarrays += (stack.length ? stack[stack.length - 1] : arrayLength) - index;
18      
19        // Push the current index onto the stack.
20        stack.push(index);
21    }
22
23    // Return the total count of valid subarrays.
24    return countValidSubarrays;
25}
26
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Time and Space Complexity

The provided code snippet defines a function validSubarrays that calculates the number of valid subarrays in a given list of integers, nums. A valid subarray here is defined such that for every element in the subarray, there is no smaller element to its right in the subarray.

Time Complexity

The time complexity of the function primarily depends on the loop and the while loop used for comparison and popping the stack.

The outer loop runs in reverse, starting from the last element of the array (n - 1) to the first one (index 0) exactly once, thus iterating n times, where n is the length of the array. For each element, the inner while loop runs only as long as there are elements in the stack and the condition nums[stk[-1]] >= nums[i] holds true.

In the worst-case scenario, each element will be pushed and popped from the stack exactly once, since an element would only be popped if a smaller element is encountered, ensuring that each pair of elements is compared at most once during the iteration. This leads to the conclusion that the complexity of both loops combined still remains O(n), because the inner while loop operations are distributing the cost of n pop operations across n iterations, which is an amortized analysis.

Hence, the time complexity of this function is O(n).

Space Complexity

The space complexity is mainly due to the additional data structure used - the stack stk. In the worst-case scenario, the stack will contain all n elements from the list nums when the list elements are in non-decreasing order. In this case, all elements will be pushed to the stack, and none will be popped until the loop is completely finished.

Therefore, the space complexity of this function 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:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

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

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

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

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 👨‍🏫