Number of Valid Subarrays

Problem

Given an integer array nums, return the number of non-emptysubarrays with the leftmost element of the subarray not larger than other elements in the subarray.

A subarray is a contiguous part of an array.

Examples

Example 1:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

Example 2:

Input: nums = [3,2,1]
Output: 3
Explanation: The 3 valid subarrays are: [3],[2],[1].

Example 3:

Input: nums = [2,2,2]
Output: 6
Explanation: There are 6 valid subarrays: [2],[2],[2],[2,2],[2,2],[2,2,2].

Constraints:

• 1 <= nums.length <= 5 * 10^4
• 0 <= nums[i] <= 10^5

Solution

Method 1 – Monotonic Stack (Next Smaller Element)

Intuition

For each index, find the farthest right index such that all elements in between are at least as large as nums[i]. This can be done efficiently using a monotonic increasing stack.

Approach

1. Initialize an empty stack and a variable ans = 0.
2. Iterate through the array. For each index, pop from the stack while nums[stack[-1]] > nums[i], and for each pop, add (i - stack[-1]) to ans.
3. After the loop, for remaining indices in the stack, add (n - idx) to ans.
4. Return ans.

Code

C++

class Solution {
public:
    int validSubarrays(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && nums[st.top()] > nums[i]) {
                ans += i - st.top();
                st.pop();
            }
            st.push(i);
        }
        while (!st.empty()) {
            ans += n - st.top();
            st.pop();
        }
        return ans;
    }
};

Go

func validSubarrays(nums []int) int {
    n, ans := len(nums), 0
    st := []int{}
    for i := 0; i < n; i++ {
        for len(st) > 0 && nums[st[len(st)-1]] > nums[i] {
            ans += i - st[len(st)-1]
            st = st[:len(st)-1]
        }
        st = append(st, i)
    }
    for len(st) > 0 {
        ans += n - st[len(st)-1]
        st = st[:len(st)-1]
    }
    return ans
}

Java

class Solution {
    public int validSubarrays(int[] nums) {
        int n = nums.length, ans = 0;
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && nums[st.peek()] > nums[i]) {
                ans += i - st.pop();
            }
            st.push(i);
        }
        while (!st.isEmpty()) {
            ans += n - st.pop();
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun validSubarrays(nums: IntArray): Int {
        val n = nums.size
        var ans = 0
        val st = ArrayDeque<Int>()
        for (i in 0 until n) {
            while (st.isNotEmpty() && nums[st.last()] > nums[i]) {
                ans += i - st.removeLast()
            }
            st.addLast(i)
        }
        while (st.isNotEmpty()) {
            ans += n - st.removeLast()
        }
        return ans
    }
}

Python

class Solution:
    def validSubarrays(self, nums: list[int]) -> int:
        n, ans = len(nums), 0
        st = []
        for i in range(n):
            while st and nums[st[-1]] > nums[i]:
                ans += i - st.pop()
            st.append(i)
        while st:
            ans += n - st.pop()
        return ans

Rust

impl Solution {
    pub fn valid_subarrays(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = 0;
        let mut st = Vec::new();
        for i in 0..n {
            while let Some(&j) = st.last() {
                if nums[j] > nums[i] {
                    ans += (i - j) as i32;
                    st.pop();
                } else {
                    break;
                }
            }
            st.push(i);
        }
        while let Some(j) = st.pop() {
            ans += (n - j) as i32;
        }
        ans
    }
}

TypeScript

class Solution {
    validSubarrays(nums: number[]): number {
        const n = nums.length
        let ans = 0
        const st: number[] = []
        for (let i = 0; i < n; i++) {
            while (st.length && nums[st[st.length-1]] > nums[i]) {
                ans += i - st.pop()!
            }
            st.push(i)
        }
        while (st.length) {
            ans += n - st.pop()!
        }
        return ans
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the length of nums.
• 🧺 Space complexity: O(n), for the stack.