Count Bowl Subarrays

medium array monotonic stack stack

Problem

You are given an integer array nums with distinct elements. A subarray nums[l..r] is a bowl if its length is at least 3 (r − l + 1 ≥ 3) and the minimum of its two ends is strictly greater than the maximum of all elements in between: min(nums[l], nums[r]) > max(nums[l+1], …, nums[r−1]). Return the number of bowl subarrays.

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

Output2

Bowls are [3,1,4] (min(3,4)=3 > max(1)=1) and [5,3,1,4] (min(5,4)=4 > max(3,1)=3).

nums (comma-separated distinct integers)

def bowlSubarrays(nums):
    stack = []            # indices, values strictly decreasing
    res = 0
    for i in range(len(nums)):
        v = nums[i]
        # pop every smaller element: v is a taller right wall
        while stack and nums[stack[-1]] < v:
            stack.pop()
            # a taller left wall still remains -> one bowl
            if stack:
                res += 1
        stack.append(i)
    return res

function bowlSubarrays(nums) {
  const stack = [];        // indices, values strictly decreasing
  let res = 0;
  for (let i = 0; i < nums.length; i++) {
    const v = nums[i];
    // pop every smaller element: v is a taller right wall
    while (stack.length && nums[stack[stack.length - 1]] < v) {
      stack.pop();
      // a taller left wall still remains -> one bowl
      if (stack.length) res += 1;
    }
    stack.push(i);
  }
  return res;
}

long bowlSubarrays(int[] nums) {
    Deque<Integer> stack = new ArrayDeque<>(); // indices, decreasing
    long res = 0;
    for (int i = 0; i < nums.length; i++) {
        int v = nums[i];
        // pop every smaller element: v is a taller right wall
        while (!stack.isEmpty() && nums[stack.peek()] < v) {
            stack.pop();
            // a taller left wall still remains -> one bowl
            if (!stack.isEmpty()) res += 1;
        }
        stack.push(i);
    }
    return res;
}

long long bowlSubarrays(vector<int>& nums) {
    vector<int> stack;        // indices, values strictly decreasing
    long long res = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        int v = nums[i];
        // pop every smaller element: v is a taller right wall
        while (!stack.empty() && nums[stack.back()] < v) {
            stack.pop_back();
            // a taller left wall still remains -> one bowl
            if (!stack.empty()) res += 1;
        }
        stack.push_back(i);
    }
    return res;
}

Explanation

A bowl needs two tall walls with everything between them strictly shorter. The trick is to realize that the only elements that can ever be an interior of some bowl are the local dips — values with a strictly taller neighbour on both the left and the right.

We sweep left to right keeping a strictly decreasing monotonic stack of indices. As long as values keep going down, we just push them. When a new value v = nums[i] is taller than the stack top, v becomes a right wall, so we pop everything shorter than it.

Each pop removes one element that is now sandwiched: the element just popped is shorter than v on its right. The moment we pop it, whatever is still on the stack is a strictly taller value to its left — a valid left wall. That left wall, the popped value (plus any earlier popped values, which are even smaller and already counted as interior), and v form exactly one bowl, so we add 1.

If the stack becomes empty during a pop, there is no taller element to the left, so that pop does not create a bowl and we skip the increment. After the while-loop ends we push i, keeping the stack decreasing.

Example: [5,1,2,3,4]. The 5 stays at the bottom forever. Each of 1, 2, 3, 4 pops the one below it while 5 remains as the left wall, giving the three bowls [5,1,2], [5,1,2,3], and [5,1,2,3,4].

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