Solution: Number of Valid Subarrays

Statement

Given an integer array nums, count how many non-empty contiguous subarrays exist where the first element of each subarray is less than or equal to every other element within that subarray.

Note: A subarray is defined as a contiguous portion of an array.

Constraints:

• $1 \leq$ nums.length $\leq 1000$

• $0 \leq$ nums[i] $\leq 10^5$

Solution

The solution efficiently counts all non-empty subarrays where the leftmost element is the smallest or equal to all other elements in that subarray. It achieves this by using a monotonic increasing stack, which maintains indices of elements such that the values at those indices are in non-decreasing order. This ensures that the element at the bottom of the stack is always less than or equal to the ones above it.

As we iterate through the array:

• If the current element is smaller than the element at the top of the stack, we pop from the stack. This tells us that the popped element has now encountered a smaller element to its right, so all subarrays that start at the popped index and end just before the current index are now complete. For each index we pop, we add (current index - popped index) to the answer, since that’s the number of valid subarrays where the popped element is the smallest and starts the subarray.

• If the current element is greater than or equal to the element at the top of the stack, we simply push its index onto the stack as it could still be a valid subarray starter.

After the full traversal, any indexes still left in the stack didn’t encounter a smaller element after them. So, for each of those, we count all subarrays that start at that index and go up to the end of the array, i.e., we add (array length - index) to the answer.

The steps of the algorithm are as follows:

1. Initialize a variable ans to 0 and an empty stack stack.

2. Traverse the array from left to right using index i:

   1. While the stack is not empty and nums[i] is less than the element at the index on top of the stack, i.e, nums[stack.peek()]:

      1. Pop the top index top from the stack.

      2. Add i - top to ans (count of valid subarrays starting at top and ending before i).

   2. Push the current index i onto the stack.

3. After the traversal, process remaining indexes in the stack:

   1. For each index top left in the stack:

      1. Add nums.length - top to ans (these elements can extend to the end).

4. Return the final value of ans.

Let’s look at the following illustration to get a better understanding of the solution: