Count Bowl Subarrays - Solution & Explanation

Problem Overview: You are given an array and must count subarrays that form a bowl shape. A valid bowl has a lower middle element with larger values on both sides, creating a valley-like structure inside the subarray.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

The most direct approach checks every possible subarray [l, r] and verifies whether it forms a bowl. For each pair of indices, iterate through the subarray to locate the minimum element and confirm that elements toward the left decrease toward it while elements toward the right increase away from it. This requires nested loops plus a validation scan, leading to O(n^3) time. It is rarely acceptable for large inputs but helps clarify the bowl definition.

Approach 2: Improved Scan with Precomputed Checks (O(n^2) time, O(1) space)

Instead of validating the entire subarray each time, fix the middle index as the potential bowl bottom and expand outward. While expanding left and right, ensure the left side strictly decreases toward the bottom and the right side strictly increases away from it. Each expansion validates potential boundaries and counts valid subarrays. This reduces redundant scanning compared with brute force but still requires checking many index pairs, resulting in O(n^2) time.

Approach 3: Monotonic Stack Boundary Analysis (O(n) time, O(n) space)

The optimal method uses a monotonic stack to quickly determine the nearest greater elements on both sides of every index. Treat each element as the potential bottom of a bowl. Using a decreasing stack, compute the nearest greater element to the left and the nearest greater element to the right. These boundaries represent the closest positions where the bowl walls can form.

Once these boundaries are known, count how many valid left endpoints exist between the bottom and its left boundary, and how many right endpoints exist between the bottom and its right boundary. The total bowls using that index as the bottom are derived from these combinations. The stack ensures each index is pushed and popped once, giving linear runtime.

This pattern appears frequently in array problems that rely on stack-based boundary discovery or monotonic ordering. Similar logic is used in histogram area problems and subarray minimum/maximum calculations over arrays.

Recommended for interviews: Interviewers expect the monotonic stack solution. Starting with brute force demonstrates understanding of the bowl definition, but the linear-time boundary computation shows strong algorithmic reasoning and familiarity with stack-based array techniques.