Number of Valid Subarrays

Number of Valid Subarrays

What is this problem about?

The Number of Valid Subarrays problem asks you to count subarrays where the minimum element is at the leftmost position. In other words, count subarrays [l..r] where arr[l] ≤ arr[i] for all i in [l..r]. This is equivalent to asking: for each starting position l, how many valid right endpoints r exist before a smaller element appears. This hard coding problem uses a monotonic stack.

Why is this asked in interviews?

Hulu and Amazon ask this because it maps directly to the "next smaller element" problem — for each l, the valid right boundary is just before the next element smaller than arr[l]. Using a monotonic stack, this is solvable in O(n). The array, monotonic stack, and stack interview pattern is the core.

Algorithmic pattern used

Monotonic stack for next smaller element. For each index l, find nextSmaller[l] = the first index r where arr[r] < arr[l]. The count of valid subarrays starting at l = nextSmaller[l] - l. Sum all these counts. Use a monotonic increasing stack to compute all nextSmaller values in O(n).

Example explanation

arr=[1,4,2,5,3]. nextSmaller:

• nextSmaller[0] (1): no smaller to right → n=5. Count=5-0=5.
• nextSmaller[1] (4): arr[2]=2<4 → nextSmaller[1]=2. Count=2-1=1.
• nextSmaller[2] (2): arr[4]=3>2, end → nextSmaller[2]=5. Count=5-2=3.
• nextSmaller[3] (5): arr[4]=3<5 → nextSmaller[3]=4. Count=4-3=1.
• nextSmaller[4] (3): no smaller → nextSmaller[4]=5. Count=5-4=1. Total = 5+1+3+1+1 = 11.

Common mistakes candidates make

• Using "≤" instead of "<" for next smaller (strict vs non-strict matters for the boundary).
• Not handling ties (equal elements at start of subarray are valid since leftmost ≤ equal).
• Computing next smaller with O(n²) nested loops.
• Off-by-one in the count: nextSmaller[l] - l (distance to next smaller, not including it).

Interview preparation tip

The monotonic stack for "next smaller element" is the foundation for many hard subarray counting problems. Once you have nextSmaller[l] for all l, subarray counting reduces to a simple sum. Practice computing next smaller, previous smaller, next greater, and previous greater element arrays using monotonic stacks — these four arrays serve as building blocks for dozens of hard problems at Amazon and Hulu.