# 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

| Item | Meaning |
|---|---|
| Input | Array `nums` |
| Output | Number of subarrays where the first element is the minimum |

Function shape:

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

## Examples

Example 1:

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

Valid subarrays:

| Start | Max end | Count |
|---|---|---|
| 0 | 4 | 5 |
| 1 | 4 | 4 |
| 2 | 4 | 3 |
| 3 | 4 | 2 |
| 4 | 4 | 1 |

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

```python
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

```python
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()
```

| Test | Expected | Why |
|---|---:|---|
| Non-decreasing | `15` | All subarrays valid |
| Decreasing | `3` | Only single-element subarrays valid |
| Equal elements | `6` | All subarrays valid |