Number of Valid Subarrays — DSA · Engineering Playbook

Problem#

Given an integer array nums, count the number of non-empty subarrays where the leftmost element is the smallest in that subarray.

Examples#

nums = [1,4,2,5,3] → 11
nums = [3,2,1] → 3
nums = [2,2,2] → 6

Constraints#

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

Approach#

For each index i, count subarrays where nums[i] is the leftmost smallest. That’s (next strictly smaller index to the right of i) - i. Compute next-smaller indices with a monotonic stack.

Solution#

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

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

from typing import List

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

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

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

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

Editorial#

A subarray [i..j] is valid iff nums[i] <= nums[k] for all i <= k <= j. For a fixed i, the maximum valid j is one less than the first index to the right with nums[k] < nums[i]. Summing those widths across i gives the answer.

Complexity#

Time: O(n).
Space: O(n).

Concept revision#

Daily Temperatures

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#