LeetCode 1063: Number of Valid Subarrays

Problem Restatement

We are given an integer array nums.

A valid subarray is one where nums[left] <= nums[i] for all left <= i <= right.

In other words, the minimum of the subarray is at the leftmost position.

Return the number of valid subarrays.

The official constraints state that 1 <= nums.length <= 50000.

Input and Output

Function shape:

def validSubarrays(nums: list[int]) -> int:
    ...

Examples

Example 1:

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

Valid subarrays:

Total: 5 + 4 + 3 + 2 + 1 = 15.

Wait, not all of those are valid. For start=0 (nums[0]=1): [1], [1,1], [1,1,2], [1,1,2,2], [1,1,2,2,3] — all valid since 1 ≤ everything. That’s 5.

For start=1 (nums[1]=1): similarly 4 subarrays.

For start=2 (nums[2]=2): [2], [2,2], [2,2,3]. That’s 3.

For start=3 (nums[3]=2): [2], [2,3]. That’s 2.

For start=4 (nums[4]=3): [3]. That’s 1.

Total: 5 + 4 + 3 + 2 + 1 = 15.

Answer: 15.

Key Insight

For each starting index i, we need the rightmost index j such that nums[k] >= nums[i] for all i <= k <= j.

This is equivalent to finding the next index where nums[j] < nums[i].

Use a monotonic stack: maintain indices in non-decreasing order of nums. For each i, pop all stack entries with nums[stack[-1]] < nums[i]. When we pop index j, the valid range for j ends at i - 1, contributing i - j subarrays.

Algorithm

1. Maintain a stack of starting indices.
2. For each i, pop indices j where nums[j] > nums[i] (those subarrays end at i-1).
3. Push i.
4. After the loop, all remaining stack entries extend to the end.

A simpler formulation is: for each index i, count how many consecutive subarrays starting at i can keep nums[i] as the minimum. That stops at the first element smaller than nums[i], so this is a next-smaller-element problem.

Edge Cases

• The stack should store exactly the unresolved items needed by the invariant.
• Process equal values deliberately; many monotonic-stack problems differ only in < versus <=.
• Flush or inspect the remaining stack after the scan if unresolved items still contribute to the answer.

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def validSubarrays(self, nums: list[int]) -> int:
        n = len(nums)
        stack = []
        result = 0

        for i in range(n):
            while stack and nums[stack[-1]] > nums[i]:
                j = stack.pop()
                result += i - j
            stack.append(i)

        while stack:
            j = stack.pop()
            result += n - j

        return result

Testing

def run_tests():
    s = Solution()

    assert s.validSubarrays([1,1,2,2,3]) == 15
    assert s.validSubarrays([3,2,1]) == 3
    assert s.validSubarrays([2,2,2]) == 6

    print("all tests passed")

run_tests()