Skip to main content
Talentd

Number of Valid Subarrays - Solution & Explanation

HardPremiumFree on FleetCodeArrayStackMonotonic Stack5 min readAsked at: Hulu
Practice this problem

Problem Statement

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 * 104
  • 0 <= nums[i] <= 105

Approach Overview

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.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ExpansionO(n²)O(1)Useful for understanding the definition of a valid subarray or when constraints are very small.
Monotonic Increasing StackO(n)O(n)Best general solution for large arrays. Each element is processed once using stack push/pop operations.

Video Solution

Number of Valid Subarrays | Leetcode 1063 • Pepcoding • 4,368 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Number of Valid Subarrays easy or hard?
The problem is labeled Hard on LeetCode even though the final algorithm is short. The challenge lies in recognizing the monotonic stack pattern and understanding why the stack size directly represents the number of valid subarrays.
Number of Valid Subarrays Python/Java solution
Most implementations follow the same monotonic stack pattern across languages. Maintain a stack, pop elements while the current value is smaller, push the current value, and add the stack size to the running total. The logic translates directly to Python, Java, C++, Go, and TypeScript.
How to solve Number of Valid Subarrays in O(n)?
Traverse the array while maintaining a monotonic increasing stack. If the current value is smaller than the stack top, pop elements until the stack becomes valid again. Push the current value and add the stack size to the result because each element in the stack forms a valid subarray start. This ensures linear processing of all elements.
What is the best approach for Number of Valid Subarrays?
The optimal solution uses a monotonic increasing stack. As you iterate through the array, you maintain elements in non-decreasing order and pop values when a smaller element appears. The stack size at each step represents how many valid subarrays end at that index. This approach runs in O(n) time and O(n) space.
Is Number of Valid Subarrays asked at Google/Amazon/Meta?
Problems involving monotonic stacks and subarray minimum constraints frequently appear in interviews at companies like Google, Amazon, and Meta. Variants such as Next Smaller Element, Sum of Subarray Minimums, and histogram problems test the same core pattern used in this question.
What data structure is used in Number of Valid Subarrays?
The key data structure is a monotonic stack that maintains elements in non-decreasing order. It allows efficient tracking of ranges where each element remains the minimum of its subarrays. This structure ensures each element is processed only once.
What is the time complexity of Number of Valid Subarrays?
The optimal monotonic stack solution runs in O(n) time because each element is pushed onto the stack once and popped at most once. The space complexity is O(n) for the stack. A naive brute force approach would take O(n²) time by expanding every subarray.

Ready to solve this problem?

Practice Number of Valid Subarrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Smooth Descent Periods of a Stock