#3676
Count Bowl Subarrays
MediumArrayStackMonotonic StackMonotonic StackArray
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n)Space O(n)
Use monotonic stacks to efficiently find the nearest greater elements on both sides, allowing us to quickly determine valid bowl subarrays.
⚙️
Algorithm
3 steps- 1Step 1: Use a monotonic stack to find the nearest greater element to the left for each index.
- 2Step 2: Use a monotonic stack to find the nearest greater element to the right for each index.
- 3Step 3: For each index, calculate the number of valid bowl subarrays using the distances to the nearest greater elements.
solution.py23 lines
1def countBowlSubarrays(nums):
2 n = len(nums)
3 left = [0] * n
4 right = [0] * n
5 stack = []
6 for i in range(n):
7 while stack and nums[stack[-1]] < nums[i]:
8 stack.pop()
9 left[i] = stack[-1] if stack else -1
10 stack.append(i)
11 stack.clear()
12 for i in range(n - 1, -1, -1):
13 while stack and nums[stack[-1]] < nums[i]:
14 stack.pop()
15 right[i] = stack[-1] if stack else n
16 stack.append(i)
17 count = 0
18 for i in range(n):
19 l = left[i] + 1
20 r = right[i] - 1
21 if r - l >= 2:
22 count += (i - l + 1) * (r - i)
23 return countℹ
Complexity note: Using stacks allows us to find the nearest greater elements in linear time, making the overall complexity linear.
- 1Bowl subarrays require careful boundary checks.
- 2Using stacks can optimize the search for conditions.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.