Number of Valid Subarrays - Solution & Explanation

Problem 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.