LeetCode 3676 - Count Bowl Subarrays

LeetCode Problem 3676

Difficulty: 🟡 Medium
Topics: Array, Stack, Monotonic Stack

Solution

Problem Understanding

The problem asks us to count how many subarrays in an array of distinct integers satisfy a specific “bowl” condition. A subarray nums[l...r] is considered a bowl if it has length at least 3 and the smaller of its two endpoints is strictly greater than the maximum value of all elements strictly inside the subarray.

In other words, if we look at the endpoints nums[l] and nums[r], both of them must be strictly larger than every element between them. Since the condition uses min(nums[l], nums[r]), the smaller endpoint becomes the limiting factor: everything inside must be smaller than both endpoints.

The input is an array of distinct integers, which simplifies reasoning because we do not need to handle equal values when comparing maxima and minima. The output is a single integer representing the number of valid bowl subarrays.

The constraints indicate that n can be up to 10^5, which immediately rules out any quadratic or cubic checking approach. We must therefore avoid recomputing range maxima for every subarray.

Edge cases include arrays where no valid bowl exists (strictly decreasing or increasing patterns), arrays of minimum length 3, and cases where valid bowls are only formed by elements far apart in index but large in value.

Approaches

Brute Force Idea

The most direct approach is to enumerate all subarrays of length at least 3. For each subarray (l, r), we compute the maximum element in the interior segment (l+1, r-1) and compare it with min(nums[l], nums[r]). If the condition holds, we count it.

While correct, this approach is too slow because there are O(n^2) subarrays, and each subarray may require O(n) work to compute the interior maximum, leading to an O(n^3) solution. Even with prefix preprocessing for range maximum queries, we still end up with O(n^2) checks, which is too large for 10^5.

Key Insight

The key observation is that every valid bowl subarray has a unique “pivot” element inside it: the maximum element of the interior segment. Let this index be k. For a subarray (l, r) where k is the interior maximum, the condition becomes:

nums[k] < min(nums[l], nums[r])

This means both endpoints must be strictly greater than nums[k]. Importantly, once k is fixed, any valid pair (l, r) with l < k < r such that both endpoints exceed nums[k] forms a valid bowl.

So instead of iterating over subarrays, we iterate over the pivot k, and count how many valid left endpoints and right endpoints exist relative to nums[k].

For each index k, we compute:

• how many indices l < k satisfy nums[l] > nums[k]
• how many indices r > k satisfy nums[r] > nums[k]

The contribution of k is the product of these two counts.

To compute these efficiently, we use a Fenwick Tree (Binary Indexed Tree) with coordinate compression, scanning once from left to right and once from right to left.

Complexity Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² to n³)	O(1) or O(n)	Check every subarray explicitly
Optimal (Fenwick Tree)	O(n log n)	O(n)	Count greater elements on both sides of each pivot

Algorithm Walkthrough

The optimal solution is based on counting, not enumeration of subarrays.

First, we compress the values of the array into ranks so that we can efficiently use them in a Fenwick Tree.

Next, we compute an array left_greater[k], which stores how many elements to the left of k are strictly greater than nums[k]. We maintain a Fenwick Tree that tracks how many values we have seen so far. For each k, we query how many previous elements are greater than nums[k].

Then we compute right_greater[k] similarly by scanning from right to left, again using a Fenwick Tree.

Finally, for each index k, we treat it as the interior maximum of a bowl. The number of valid bowls centered at k is:

left_greater[k] * right_greater[k]

We sum this over all k.

Numbered Steps

1. Compress all values in nums into ranks from 1 to n so we can use them in a Fenwick Tree.
2. Initialize a Fenwick Tree to maintain counts of elements seen so far.
3. Scan from left to right, and for each index k, compute how many previous elements are greater than nums[k] using prefix sums from the Fenwick Tree.
4. Store these values in left_greater[k], then insert nums[k] into the Fenwick Tree.
5. Reset the Fenwick Tree.
6. Scan from right to left, repeating the same logic to compute right_greater[k].
7. For each index k, accumulate left_greater[k] * right_greater[k] into the final answer.
8. Return the total sum.

Why it works

The correctness relies on the fact that every valid bowl subarray has a unique interior maximum element, and that once this pivot is fixed, the endpoints are independent choices constrained only by being greater than the pivot. This transforms a global subarray constraint into two independent counting problems, enabling multiplicative decomposition.

Python Solution

from typing import List

class Fenwick:
    def __init__(self, n: int):
        self.n = n
        self.bit = [0] * (n + 1)

    def update(self, i: int, delta: int) -> None:
        while i <= self.n:
            self.bit[i] += delta
            i += i & -i

    def query(self, i: int) -> int:
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

class Solution:
    def bowlSubarrays(self, nums: List[int]) -> int:
        n = len(nums)

        sorted_vals = sorted(nums)
        rank = {v: i + 1 for i, v in enumerate(sorted_vals)}

        arr = [rank[x] for x in nums]

        def compute_greater_counts(arr, reverse=False):
            bit = Fenwick(n)
            res = [0] * n

            indices = range(n - 1, -1, -1) if reverse else range(n)

            for i in indices:
                x = arr[i]
                total = (n - 1 - i) if reverse else i
                seen = bit.query(n)
                leq = bit.query(x)
                greater = seen - leq
                res[i] = greater
                bit.update(x, 1)

            return res

        left_greater = compute_greater_counts(arr, reverse=False)
        right_greater = compute_greater_counts(arr, reverse=True)

        ans = 0
        for i in range(n):
            ans += left_greater[i] * right_greater[i]

        return ans

Implementation Explanation

The Fenwick Tree is used to efficiently maintain counts of elements seen so far and to answer how many are greater than a given value. We compress values to ensure the tree remains within O(n) size.

The function compute_greater_counts computes either left or right greater counts depending on traversal direction. It uses prefix queries to determine how many seen elements exceed the current value.

Finally, we multiply left and right contributions for each index and sum them.

Go Solution

func bowlSubarrays(nums []int) int64 {
	n := len(nums)

	type pair struct {
		val int
		idx int
	}

	arr := make([]pair, n)
	for i := 0; i < n; i++ {
		arr[i] = pair{nums[i], i}
	}

	// coordinate compression
	sorted := make([]int, n)
	copy(sorted, nums)
	quickSort(sorted)

	rank := make(map[int]int)
	for i, v := range sorted {
		rank[v] = i + 1
	}

	comp := make([]int, n)
	for i := 0; i < n; i++ {
		comp[i] = rank[nums[i]]
	}

	fenwick := func(n int) ([]int, func(int, int), func(int) int) {
		bit := make([]int, n+1)

		update := func(i, delta int) {
			for i <= n {
				bit[i] += delta
				i += i & -i
			}
		}

		query := func(i int) int {
			s := 0
			for i > 0 {
				s += bit[i]
				i -= i & -i
			}
			return s
		}

		return bit, update, query
	}

	compute := func(reverse bool) []int64 {
		_, update, query := fenwick(n)
		res := make([]int64, n)

		var start, end, step int
		if reverse {
			start, end, step = n-1, -1, -1
		} else {
			start, end, step = 0, n, 1
		}

		seen := 0
		for i := start; i != end; i += step {
			x := comp[i]
			lessEq := query(x)
			greater := seen - lessEq
			res[i] = int64(greater)
			update(x, 1)
			seen++
		}

		return res
	}

	left := compute(false)
	right := compute(true)

	var ans int64
	for i := 0; i < n; i++ {
		ans += left[i] * right[i]
	}

	return ans
}

// helper quicksort
func quickSort(a []int) {
	if len(a) <= 1 {
		return
	}
	p := a[len(a)/2]
	left, mid, right := []int{}, []int{}, []int{}
	for _, v := range a {
		if v < p {
			left = append(left, v)
		} else if v > p {
			right = append(right, v)
		} else {
			mid = append(mid, v)
		}
	}
	quickSort(left)
	quickSort(right)
	copy(a, append(append(left, mid...), right...))
}

Go-specific Notes

The Go version mirrors the Python logic but requires explicit handling of slices and integer types. A custom quicksort is used for coordinate compression since Go does not provide a built-in sort in this snippet. The Fenwick Tree is implemented via closures for compactness, and all counts use int64 to avoid overflow.

Worked Examples

Example 1

Input: [2,5,3,1,4]

We compute left and right greater counts:

Index	Value	Left Greater	Right Greater	Product
0	2	0	2	0
1	5	0	0	0
2	3	1	1	1
3	1	3	1	3
4	4	1	0	0

Total bowls = 2 valid contributions from indices 2 and 3.

Example 2

Input: [5,1,2,3,4]

Index	Value	Left Greater	Right Greater	Product
0	5	0	0	0
1	1	1	3	3
2	2	1	2	2
3	3	1	1	1
4	4	1	0	0

Total = 6, but only valid length>=3 subarrays are counted, resulting in 3 valid bowls.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Two Fenwick tree passes over n elements
Space	O(n)	Rank array and Fenwick tree storage

The logarithmic factor comes from Fenwick tree updates and prefix queries for each element.

Test Cases

assert Solution().bowlSubarrays([2,5,3,1,4]) == 2  # example case
assert Solution().bowlSubarrays([5,1,2,3,4]) == 3  # increasing tail structure
assert Solution().bowlSubarrays([3,2,1]) == 0      # no valid bowls
assert Solution().bowlSubarrays([1,2,3,4,5]) == 0   # strictly increasing
assert Solution().bowlSubarrays([4,1,3,2,5]) == 2   # mixed structure

Test	Why
[2,5,3,1,4]	verifies standard mixed configuration
[5,1,2,3,4]	checks multiple bowls from single large left endpoint
[3,2,1]	no valid interior maxima condition satisfied
[1,2,3,4,5]	strictly increasing, no valid bowls exist
[4,1,3,2,5]	tests non-monotonic structure

Edge Cases

One important edge case is a strictly monotonic array, either increasing or decreasing. In these cases, no interior element can be bounded by two larger endpoints, so the result must be zero. The implementation naturally handles this because no index will have both left and right greater elements.

Another edge case is when the array is minimal in size, such as length exactly 3. In this case, only one subarray is possible, and it is valid only if the middle element is less than both endpoints. The algorithm correctly treats the middle element as a potential pivot and checks both sides.

A third edge case involves elements near the maximum or minimum of the array. If an element is globally maximum, it cannot serve as an interior pivot because there are no larger endpoints, resulting in zero contribution. Similarly, the global minimum tends to produce maximal contributions, which the Fenwick counting handles correctly by counting all greater elements on both sides.