MediumStacks QueuesAI interview only
Count Bowl Subarrays
Asked atamazongooglebloomberg
01 · Problem
You are given an array nums of distinct integers. A subarray nums[l..r] is called a bowl when:
- its length is at least
3(that is,r - l + 1 >= 3), and - both endpoints are strictly larger than every element strictly between them:
min(nums[l], nums[r]) > max(nums[l + 1..r - 1]).
Return the number of bowl subarrays in nums.
02 · Examples
Example 01
Input
nums = [4,1,3,2,6]
Output
3
The bowls are [4,1,3], [3,2,6] and the whole array [4,1,3,2,6] (both 4 and 6 exceed every middle value).
Example 02
Input
nums = [6,2,1,7]
Output
2
The bowls are [2,1,7] and [6,2,1,7]. [6,2,1] is not a bowl because its endpoint 1 is smaller than the middle 2.
Example 03
Input
nums = [1,2,3]
Output
0
The only length-3 subarray has endpoint 1, which is smaller than the middle element 2, so there are no bowls.
03 · Constraints
- 013 <= nums.length <= 105
- 021 <= nums[i] <= 109
- 03All values in nums are distinct
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.