Practice Find the Number of Subarrays Where Boundary Elements Are Maximum
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Find the Number of Subarrays Where Boundary Elements Are Maximum
Problem Statement
You are given an array of positive integers nums. Return the number of subarrays of nums, where the first and the last elements of the subarray are equal to the largest element in the subarray.
Source: Find the Number of Subarrays Where Boundary Elements Are Maximum on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
nums = [1,4,3,3,2]
6
Each of the five one-element subarrays qualifies because its only value is both boundaries and the maximum. The only additional qualifying subarray is [3,3] at zero-based positions 2 through 3. These are the only repeated values in the array, so no other longer subarray can have equal boundaries. The total is 5 + 1 = 6. In general, equal endpoints are necessary but not sufficient: an interior value larger than the endpoints would invalidate the subarray.
# Example 2
nums = [3,3,3]
6
All elements equal 3, so every contiguous subarray has first value, last value, and maximum equal to 3. Count three subarrays of length 1, two of length 2, and one of length 3: 3 + 2 + 1 = 6. The two length-2 occurrences count separately even though both contain [3,3], because they occupy different positions. More generally, a run of m equal values has m(m + 1)/2 subarrays; counting only distinct value sequences would undercount.
# Example 3
nums = [1]
1
The only nonempty subarray is [1]. Its first and last elements are the same element, and its maximum is also 1, so it qualifies. The answer is 1. Boundary elements do not have to occupy different positions; an implementation that counts only pairs of distinct indices would incorrectly omit every one-element subarray.
Constraints
How to solve Find the Number of Subarrays Where Boundary Elements Are Maximum
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
A subarray qualifies exactly when its ends are equal and nothing strictly between them is larger. A left-to-right scan with a nonincreasing monotonic stack of (value, count) pairs lets each element see precisely the earlier equal elements not blocked by a larger value, and those are the valid left endpoints it closes.
Why brute force is not enough
Enumerating all O(n^2) subarrays with a running maximum is O(n^2); with nums.length up to 10^5 that is around 10^10 operations.
Approach
- Keep a stack with values nonincreasing from bottom to top, each entry storing a value and the number of its occurrences still visible.
- For each element x, pop every entry with value strictly less than x; those values can never be left endpoints for x or anything after it, because x now blocks them.
- If the top now equals x, add its count to the answer, since everything between those occurrences and x is at most x, then increment the count. Otherwise push (x, 1).
- Add 1 for the single-element subarray at x. The invariant is that the stack holds, for every visible value, the number of positions that can pair with a future equal element.
Walkthrough of Example 1
nums = [1,4,3,3,2] → 6
- Read 1: push (1, 1); count the singleton, answer 1.
- Read 4: pop (1, 1) since 1 < 4; push (4, 1); answer 2.
- Read 3: top 4 is larger, push (3, 1); answer 3.
- Read 3: top is (3, 1) with equal value, so add 1 for [3,3] and bump to (3, 2); add the singleton. Answer 5.
- Read 2: top 3 is larger, push (2, 1); answer 6.
Time and space
Time O(n) · Space O(n). Each of the n elements is pushed and popped at most once, and the stack holds at most n entries for a strictly decreasing array.
Interview pitfalls
- Popping entries less than or equal to x instead of strictly less, which destroys the count of equal predecessors.
- Forgetting the singleton contribution; a one-element array must return 1.
- Pushing one entry per occurrence rather than aggregating equal values with a count, making the equal-value step linear and risking timeouts on arrays of identical values.
- Using a 32-bit accumulator; 10^5 equal values yield about 5 * 10^9 subarrays.
- Treating equal endpoints as sufficient; in [3, 5, 3] the two 3s do not qualify because 5 lies between them.
Follow-up questions interviewers ask
- How would you count subarrays whose boundary elements equal the subarray minimum instead?
- How would you maintain the count under point updates?
- Can you solve it by grouping positions of each value and binary searching previous-greater positions, and how do the constants compare?
Further reading on the technique: Stack (abstract data type)
Related LeetCode Problems
Practice more problems similar to Find the Number of Subarrays Where Boundary Elements Are Maximum.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.