Watch 9 video solutions for Number of Valid Subarrays, a hard level problem involving Array, Stack, Monotonic Stack. This walkthrough by Pepcoding has 4,336 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array nums, return the number of non-empty subarrays with the leftmost element of the subarray not larger than other elements in the subarray.
A subarray is a contiguous part of an array.
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 * 1040 <= nums[i] <= 105Problem Overview: You are given an integer array nums. A subarray is considered valid if the first element is less than or equal to every other element inside that subarray. The task is to count how many such subarrays exist.
Approach 1: Brute Force Expansion (O(n²) time, O(1) space)
Start every subarray at index i and expand the right boundary j one step at a time. As long as nums[j] is greater than or equal to nums[i], the subarray remains valid. The moment a smaller element appears, stop extending because the first element is no longer the minimum. This approach checks each starting index independently and may scan nearly the entire remaining array for every i. It works for small inputs but becomes too slow for large arrays due to its quadratic time complexity.
Approach 2: Monotonic Increasing Stack (O(n) time, O(n) space)
The optimal solution uses a monotonic stack to track increasing elements while scanning the array from left to right. Maintain a stack where values stay in non-decreasing order. When the current element nums[i] is smaller than the top of the stack, pop elements until the order is restored. Each pop represents a previous element whose valid range has ended because a smaller value appeared.
After adjusting the stack, push the current element. The number of valid subarrays ending at this position equals the current stack size. Why this works: every element remaining in the stack represents a starting point whose minimum condition still holds for the current index. Summing the stack sizes across the traversal gives the total number of valid subarrays.
This pattern appears frequently in array problems where you need to maintain local minimum or maximum constraints efficiently. The stack guarantees that each element is pushed once and popped at most once, which keeps the algorithm linear. The technique is also closely related to classic stack-based problems like Next Smaller Element and histogram area calculations.
Recommended for interviews: Interviewers typically expect the monotonic stack solution. The brute force method demonstrates that you understand the constraint defining a valid subarray, but it fails to scale. Recognizing that a decreasing element invalidates earlier ranges leads directly to the stack-based optimization and shows strong algorithmic pattern recognition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Expansion | O(n²) | O(1) | Useful for understanding the definition of a valid subarray or when constraints are very small. |
| Monotonic Increasing Stack | O(n) | O(n) | Best general solution for large arrays. Each element is processed once using stack push/pop operations. |