Number of Valid Subarrays

hard monotonic stack array stack

Problem

Given an integer array nums, return the number of non-empty subarrays in which the leftmost element of the subarray is not larger than every other element in that subarray (i.e. the first element is the minimum of the subarray).

Inputnums = [1, 4, 2, 5, 3]

Output11

Every subarray starting at index i is valid until the first strictly smaller value to its right. Those counts are 5, 1, 3, 1, 1, which sum to 11.

nums (comma-separated)

def valid_subarrays(nums):
    n = len(nums)
    stack = []          # indices, values increasing bottom -> top
    total = 0
    for i in range(n):
        while stack and nums[i] < nums[stack[-1]]:
            j = stack.pop()
            total += i - j
        stack.append(i)
    while stack:
        total += n - stack.pop()
    return total

function validSubarrays(nums) {
  const n = nums.length;
  const stack = [];      // indices, values increasing
  let total = 0;
  for (let i = 0; i < n; i++) {
    while (stack.length && nums[i] < nums[stack[stack.length - 1]]) {
      total += i - stack.pop();
    }
    stack.push(i);
  }
  while (stack.length) total += n - stack.pop();
  return total;
}

class Solution {
    public int validSubarrays(int[] nums) {
        int n = nums.length, total = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                total += i - stack.pop();
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) total += n - stack.pop();
        return total;
    }
}

int validSubarrays(vector<int>& nums) {
    int n = (int)nums.size(), total = 0;
    vector<int> stack;     // indices, values increasing
    for (int i = 0; i < n; i++) {
        while (!stack.empty() && nums[i] < nums[stack.back()]) {
            total += i - stack.back();
            stack.pop_back();
        }
        stack.push_back(i);
    }
    while (!stack.empty()) { total += n - stack.back(); stack.pop_back(); }
    return total;
}

Explanation

A subarray is "valid" when its first element is the smallest in it. So for each starting index i, the valid subarrays stretch right until they hit the first value strictly smaller than nums[i]. The number of valid subarrays starting at i equals the distance to that smaller value.

We find all these distances in one pass with a monotonic increasing stack of indices (values increase from bottom to top). When the current value nums[i] is smaller than the value at the stack top index j, position i is the first smaller element for j, so j contributes i - j valid subarrays.

We pop and add i - j for every such j, then push i. Indices that remain on the stack at the end never met a smaller value, so they extend all the way to the end: each contributes n - j.

Example: nums = [1, 4, 2, 5, 3]. The per-start counts work out to 5, 1, 3, 1, 1. For instance, index 0 (value 1) is never beaten, so it spans all 5 positions; index 1 (value 4) is stopped immediately by the 2, contributing just 1.

Adding these counts gives 5 + 1 + 3 + 1 + 1 = 11, the total number of valid subarrays.

Time: O(n) Space: O(n)