Skip to main content
Talentd

Find the Number of Subarrays Where Boundary Elements Are Maximum - Solution & Explanation

HardArrayBinary SearchStackMonotonic Stack20 min readAsked at: Amazon, LinkedIn
Practice this problem

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.

 

Example 1:

Input: nums = [1,4,3,3,2]

Output: 6

Explanation:

There are 6 subarrays which have the first and the last elements equal to the largest element of the subarray:

  • subarray [1,4,3,3,2], with its largest element 1. The first element is 1 and the last element is also 1.
  • subarray [1,4,3,3,2], with its largest element 4. The first element is 4 and the last element is also 4.
  • subarray [1,4,3,3,2], with its largest element 3. The first element is 3 and the last element is also 3.
  • subarray [1,4,3,3,2], with its largest element 3. The first element is 3 and the last element is also 3.
  • subarray [1,4,3,3,2], with its largest element 2. The first element is 2 and the last element is also 2.
  • subarray [1,4,3,3,2], with its largest element 3. The first element is 3 and the last element is also 3.

Hence, we return 6.

Example 2:

Input: nums = [3,3,3]

Output: 6

Explanation:

There are 6 subarrays which have the first and the last elements equal to the largest element of the subarray:

  • subarray [3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.
  • subarray [3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.
  • subarray [3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.
  • subarray [3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.
  • subarray [3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.
  • subarray [3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.

Hence, we return 6.

Example 3:

Input: nums = [1]

Output: 1

Explanation:

There is a single subarray of nums which is [1], with its largest element 1. The first element is 1 and the last element is also 1.

Hence, we return 1.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

Approach Overview

Problem Overview: You are given an integer array and must count subarrays where the first and last elements are equal and also represent the maximum value inside that subarray. Any element between the boundaries must be less than or equal to those boundary values.

Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)

Enumerate every possible subarray using two indices i and j. For each subarray, compute the maximum value and check whether both boundary elements equal that maximum. This requires iterating through the elements inside the window or maintaining a running maximum while expanding j. The approach is straightforward and helps verify the definition of the constraint, but it becomes slow for large arrays since there are O(n^2) candidate subarrays.

Approach 2: Optimized Counting with Monotonic Stack (O(n) time, O(n) space)

The key observation: a valid subarray must have its maximum at both boundaries, meaning no element inside the range can exceed that value. A monotonic stack helps maintain a decreasing structure of elements while scanning the array. When you encounter a larger value, smaller elements are popped because they cannot serve as boundaries for future subarrays containing that larger value. For elements with the same value, maintain counts of how many times that value has appeared consecutively within the valid range. Each new equal element forms additional valid subarrays with previous occurrences of the same value. This converts the problem from enumerating ranges to counting combinations of equal maximum boundaries while preserving the decreasing stack property.

The stack ensures that all elements between equal boundaries remain smaller or equal. Each push/pop operation occurs once, giving linear complexity. The approach leverages concepts from stack processing and monotonic structures commonly used for next-greater-element style problems.

Recommended for interviews: Start by describing the brute force approach to demonstrate understanding of the constraint that boundary elements must equal the subarray maximum. Interviewers expect the optimized monotonic stack counting approach because it reduces the complexity from O(n^2) to O(n). Recognizing the connection to next greater element patterns and counting equal values within the stack shows strong mastery of array processing techniques.

Approach 1: Brute Force Approach

This approach involves checking every possible subarray in the array. For each subarray, we will check if the first and last elements are equal to the maximum element of that subarray, and if so, count it as a valid subarray.

The function count_subarrays iterates over all subarray starting indices i. For each i, it iterates over all ending indices j, updating the current subarray's maximum element. If both the boundary elements of the current subarray are equal to this maximum, the subarray is counted.

Code

PythonCJavaC#JavaScript

Python

C

Java

C#

JavaScript

Complexity

Time Complexity: O(n^3), where n is the length of the array, as we compute the maximum for each subarray in a nested manner.
Space Complexity: O(1), as we are using constant space.

Try this approach in the editor →

Approach 2: Optimized Counting Using Sliding Window

This method takes advantage of consecutive segments of the array where the maximum element appears. By counting these segments, we can efficiently determine the number of valid subarrays.

The count_subarrays_optimized function first determines the maximum value in the array. It then iterates through the array, counting consecutive segments of the maximum value and updates the total count using the mathematical sum formula.

Code

PythonCJavaC#JavaScript

Python

C

Java

C#

JavaScript

Complexity

Time Complexity: O(n), as we iterate through the array once.
Space Complexity: O(1), constant space is required.

Try this approach in the editor →

Approach 3: Monotonic Stack

We consider each element x in the array nums as the boundary element and the maximum value of the subarray.

Each subarray of length 1 meets the condition, and for subarrays with length greater than 1, all elements in the subarray cannot be greater than the boundary element x. We can implement this with a monotonic stack.

We maintain a stack that decreases monotonically from the bottom to the top. Each element in the monotonic stack is a pair [x, cnt], representing the element x and the count cnt of subarrays with x as the boundary element and the maximum value.

We traverse the array nums from left to right. For each element x, we continuously pop the top element of the stack until the stack is empty or the first element of the top element of the stack is greater than or equal to x. If the stack is empty, or the first element of the top element of the stack is greater than x, it means that we have encountered the first subarray with x as the boundary element and the maximum value, and the length of this subarray is 1, so we push [x, 1] into the stack. If the first element of the top element of the stack is equal to x, it means that we have encountered a subarray with x as the boundary element and the maximum value, and we add 1 to the second element of the top element of the stack. Then, we add the second element of the top element of the stack to the answer.

After the traversal, we return the answer.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n^3), where n is the length of the array, as we compute the maximum for each subarray in a nested manner.
Space Complexity: O(1), as we are using constant space.

Optimized Counting Using Sliding Window

Time Complexity: O(n), as we iterate through the array once.
Space Complexity: O(1), constant space is required.

Monotonic Stack—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n^2)O(1)Useful for understanding the condition and validating correctness on small arrays
Monotonic Stack CountingO(n)O(n)Best general solution for large inputs; leverages decreasing stack and equal-value counting

Video Solution

3113. Find the Number of Subarrays Where Boundary Elements Are Maximum | Binary Search | Monotonic • Aryan Mittal • 4,254 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Number of Subarrays Where Boundary Elements Are Maximum easy or hard?
LeetCode classifies this problem as Hard because recognizing the monotonic stack counting pattern is not obvious. A brute force solution is straightforward but inefficient at O(n^2). Achieving the optimal O(n) solution requires deeper understanding of stack-based array algorithms.
Find the Number of Subarrays Where Boundary Elements Are Maximum Python/Java solution
Python and Java implementations typically maintain a stack storing pairs of (value, count). While traversing the array, smaller values are popped and equal values increase the count, which contributes to the number of valid subarrays. This stack-based counting approach achieves O(n) time complexity and works efficiently for large inputs.
How to solve Find the Number of Subarrays Where Boundary Elements Are Maximum in O(n)?
Use a monotonic decreasing stack while iterating through the array. When a new element is larger than the stack top, pop smaller elements because they cannot remain maximum boundaries. If the value equals the stack top, increase a counter representing how many identical boundaries exist and add that count to the result. Each operation is constant amortized time, giving O(n) complexity.
What is the best approach for Find the Number of Subarrays Where Boundary Elements Are Maximum?
The most efficient approach uses a monotonic decreasing stack to track candidate boundary elements. While scanning the array, smaller elements are removed when a larger value appears, ensuring that the remaining elements can still act as maximum boundaries. Equal values are grouped and counted to form valid subarrays. This method runs in O(n) time with O(n) auxiliary space.
Is Find the Number of Subarrays Where Boundary Elements Are Maximum asked at Google/Amazon/Meta?
Problems involving monotonic stacks and counting subarrays with boundary constraints frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include counting subarrays with maximum or minimum boundaries, next greater element patterns, and monotonic stack optimizations.
What data structure is used in Find the Number of Subarrays Where Boundary Elements Are Maximum?
The core data structure is a monotonic stack that maintains elements in decreasing order. This structure efficiently tracks candidate maximum values and removes invalid elements when larger values appear. Arrays are used for traversal while the stack enables linear-time processing.
What is the time complexity of Find the Number of Subarrays Where Boundary Elements Are Maximum?
The optimal solution runs in O(n) time because each element is pushed and popped from the monotonic stack at most once. Space complexity is O(n) for the stack used to maintain decreasing order and count equal values.

Ready to solve this problem?

Practice Find the Number of Subarrays Where Boundary Elements Are Maximum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Subarrays Where Max Element Appears at Least K Times

Next

Count Subarrays With Fixed Bounds