Find the Number of Subarrays Where Boundary Elements Are Maximum
Find the Number of Subarrays Where Boundary Elements Are Maximum solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find the Number of Subarrays Where Boundary Elements Are Maximum is a hard coding problem on arrays, binary search and stack, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Binary Search, Stack, Monotonic Stack
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of positive integers nums, count the subarrays whose first and last elements are both equal to the largest element of that subarray.
A single element is such a subarray on its own.
(The length bound below is tighter than the original problem's so that the count fits in a 32-bit integer.)
Example 1
Input: nums = [2,5,2,5,1]
Output: 6
Explanation: The five single elements, plus `[5,2,5]`. `[2,5,2]` does not count: its largest element is 5.
Example 2
Input: nums = [4,4,4]
Output: 6
Explanation: Every subarray qualifies.
Example 3
Input: nums = [3,1,3,1,3]
Output: 8
Explanation: Five singles plus `[3,1,3]` twice and the whole array.
Constraints
1 <= nums.length <= 6 * 10^41 <= nums[i] <= 10^9
Hints for Find the Number of Subarrays Where Boundary Elements Are Maximum
Hint 1
Fix the right end
j. Which left endsiwork?nums[i]must equalnums[j]and nothing between them may be larger.Hint 2
So you need, for the current value, how many equal values appear since the last strictly larger value.
Hint 3
Keep a stack of
(value, count)with strictly decreasing values. Forx, pop smaller values; if the top equalsx, increment its count, otherwise push(x, 1). Add the top's count to the answer.
How to solve Find the Number of Subarrays Where Boundary Elements Are Maximum
A valid subarray ending at j starts at an earlier copy of nums[j] with no larger value in between. A monotonic stack that merges equal values keeps exactly that count for the current value.
Approach
- Keep a stack of pairs
(value, count)with strictly decreasing values from bottom to top. - For each
x: pop while the top's value is smaller thanx— those values are now blocked byxforever. - If the top's value equals
x, increment its count; otherwise push(x, 1). - The top's count is the number of valid subarrays ending at this position; add it to the answer.
Why it works
After processing position j, the top entry for value nums[j] counts the occurrences of nums[j] since the most recent strictly larger element — any older copy is separated from j by something larger and was removed when that larger value popped it. Each such occurrence is a valid left end, and no other left end is valid, so the per-position additions sum to the answer.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Pop only strictly smaller values; equal values must be merged, not discarded.
- Each position contributes at least 1 — the single-element subarray.
- An all-equal array gives n(n+1)/2 subarrays, which is why the length is capped here.
Reference solution
Python
from typing import List
def numberOfSubarrays(nums: List[int]) -> int:
st = [] # [value, count], values strictly decreasing
ans = 0
for x in nums:
while st and st[-1][0] < x:
st.pop()
if st and st[-1][0] == x:
st[-1][1] += 1
else:
st.append([x, 1])
ans += st[-1][1]
return ansJava
public static int numberOfSubarrays(int[] nums) {
int n = nums.length;
int[] vals = new int[n], cnts = new int[n];
int top = 0;
long ans = 0;
for (int x : nums) {
while (top > 0 && vals[top - 1] < x) top--;
if (top > 0 && vals[top - 1] == x) {
cnts[top - 1]++;
} else {
vals[top] = x;
cnts[top] = 1;
top++;
}
ans += cnts[top - 1];
}
return (int) ans;
}C++
int numberOfSubarrays(vector<int>& nums) {
vector<pair<int, int>> st;
long long ans = 0;
for (int x : nums) {
while (!st.empty() && st.back().first < x) st.pop_back();
if (!st.empty() && st.back().first == x) {
st.back().second++;
} else {
st.push_back(make_pair(x, 1));
}
ans += st.back().second;
}
return (int)ans;
}JavaScript
var numberOfSubarrays = function(nums) {
var vals = [], cnts = [];
var ans = 0;
for (var i = 0; i < nums.length; i++) {
var x = nums[i];
while (vals.length > 0 && vals[vals.length - 1] < x) { vals.pop(); cnts.pop(); }
if (vals.length > 0 && vals[vals.length - 1] === x) {
cnts[cnts.length - 1]++;
} else {
vals.push(x);
cnts.push(1);
}
ans += cnts[cnts.length - 1];
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search