LeetCode 1063 - Number of Valid Subarrays

Difficulty: 🔴 Hard
Topics: Array, Stack, Monotonic Stack

Solution

Problem Understanding

The problem is asking us to count the number of valid subarrays in a given integer array nums. A subarray is valid if its leftmost element is not larger than any other element in the subarray. In other words, for a subarray starting at index i and ending at index j, the condition nums[i] <= nums[k] must hold for every k between i and j inclusive.

The input is a single array nums of integers. The output is a single integer representing the total number of non-empty subarrays that satisfy this condition. The array length can go up to 5 * 10^4 and the values up to 10^5, so a naive brute-force approach that checks all subarrays explicitly would be too slow.

Important edge cases include arrays that are strictly decreasing (like [3,2,1]), strictly increasing, or with all equal elements. These can test whether the algorithm correctly counts subarrays without overcounting or missing cases. The problem guarantees that the array is non-empty, so we do not have to handle an empty input.

Approaches

The brute-force approach would be to enumerate all possible subarrays, check for each subarray whether the leftmost element is smaller than or equal to all other elements, and count those that satisfy the condition. This is correct but inefficient, as there are O(n²) subarrays and checking each subarray takes O(n) time in the worst case, giving a total complexity of O(n³), which is infeasible for n up to 50,000.

The optimal approach leverages a monotonic stack to efficiently count valid subarrays starting from each element. The key insight is that for each element, the valid subarray extends from that element to the right until an element smaller than it is encountered. By iterating from the end of the array and using a stack to keep track of elements in non-decreasing order, we can calculate the number of valid subarrays in O(n) time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Enumerate all subarrays and check validity explicitly
Optimal	O(n)	O(n)	Use monotonic stack to count subarrays efficiently

Algorithm Walkthrough

Initialize an empty stack and a variable count to accumulate the total number of valid subarrays.
Iterate through the array from the end to the start. This ensures that when processing an element, all elements to its right have already been considered.
For each element nums[i], initialize a variable length to 1 representing the subarray consisting of the element itself.
While the stack is not empty and the top element of the stack is greater than or equal to nums[i], pop it and add its count to length. This step extends the current subarray to include contiguous elements that are greater than or equal to nums[i].
Push the current element along with its length onto the stack. This maintains the stack as a decreasing sequence by value.
Add length to count. This represents all valid subarrays starting at the current element.
Continue to the next element until the beginning of the array is reached.
Return count as the total number of valid subarrays.

Why it works: The stack keeps track of elements that form valid subarrays extending to the right. Each element contributes exactly the number of subarrays that start at it and satisfy the condition, ensuring all valid subarrays are counted once. The invariant is that the stack contains pairs of (element value, count of valid subarrays starting there), maintaining correctness efficiently.

Python Solution

from typing import List

class Solution:
    def validSubarrays(self, nums: List[int]) -> int:
        stack = []  # stack of pairs (num, count of valid subarrays starting here)
        count = 0
        for i in range(len(nums) - 1, -1, -1):
            length = 1
            while stack and stack[-1][0] >= nums[i]:
                length += stack.pop()[1]
            stack.append((nums[i], length))
            count += length
        return count

The Python implementation uses a stack to efficiently merge contiguous elements that satisfy the non-decreasing requirement. By iterating from right to left, it avoids repeatedly checking elements on the right, leveraging precomputed subarray counts stored in the stack.

Go Solution

func validSubarrays(nums []int) int {
    type pair struct {
        val int
        count int
    }
    stack := []pair{}
    total := 0
    for i := len(nums) - 1; i >= 0; i-- {
        length := 1
        for len(stack) > 0 && stack[len(stack)-1].val >= nums[i] {
            length += stack[len(stack)-1].count
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, pair{nums[i], length})
        total += length
    }
    return total
}

In Go, we define a small struct pair to store the element and the number of valid subarrays starting at it. Slice operations replace stack operations, and integer arithmetic is straightforward since the constraints are well within int limits.

Worked Examples

Example 1: nums = [1,4,2,5,3]

i	nums[i]	Stack (val,count)	length	count
4	3	[(3,1)]	1	1
3	5	[(3,1),(5,1)]	1	2
2	2	[(2,2),(5,1)]	2	4
1	4	[(4,1),(2,2),(5,1)]	1	5
0	1	[(1,5),(4,1),(2,2),(5,1)]	5	10

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

i	nums[i]	Stack (val,count)	length	count
2	1	[(1,1)]	1	1
1	2	[(2,1),(1,1)]	1	2
0	3	[(3,1),(2,1),(1,1)]	1	3

Example 3: nums = [2,2,2]

i	nums[i]	Stack (val,count)	length	count
2	2	[(2,1)]	1	1
1	2	[(2,2)]	2	3
0	2	[(2,3)]	3	6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is pushed and popped from the stack at most once.
Space	O(n)	Stack can store up to n elements in the worst case.

The linear time complexity is achieved by the monotonic stack approach, avoiding nested loops over subarrays.

Test Cases

# Provided examples
assert Solution().validSubarrays([1,4,2,5,3]) == 11  # mixed elements
assert Solution().validSubarrays([3,2,1]) == 3       # strictly decreasing
assert Solution().validSubarrays([2,2,2]) == 6       # all equal

# Edge cases
assert Solution().validSubarrays([1]) == 1           # single element
assert Solution().validSubarrays([1,2,3,4,5]) == 15 # strictly increasing
assert Solution().validSubarrays([5,4,3,2,1]) == 5  # strictly decreasing
assert Solution().validSubarrays([1,3,2,4,2,5]) == 14 # mixed with repeats

Test	Why
[1,4,2,5,3]	Tests mixed increases and decreases
[3,2,1]	Checks strictly decreasing array
[2,2,2]	All equal elements, tests merging subarrays
[1]	Single element, minimal input
[1,2,3,4,5]	Strictly increasing, every subarray valid
[5,4,3,2,1]	Strictly decreasing, only single elements valid
[1,3,2,4,2,5]	Complex mixed array, tests multiple merges

Edge Cases

The first edge case is a single-element array. The algorithm must correctly return 1, and the stack logic naturally handles this without additional checks because the loop still executes once and adds one to the count.

The second edge case is an array with all equal elements. Here, each element can extend over all contiguous equal elements, so the algorithm must correctly merge counts in the stack. Our implementation sums counts from popped elements, ensuring the total number of subarrays is correct.

The third edge case is a strictly decreasing array