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:
[1,4,3,3,2], with its largest element 1. The first element is 1 and the last element is also 1.[1,4,3,3,2], with its largest element 4. The first element is 4 and the last element is also 4.[1,4,3,3,2], with its largest element 3. The first element is 3 and the last element is also 3.[1,4,3,3,2], with its largest element 3. The first element is 3 and the last element is also 3.[1,4,3,3,2], with its largest element 2. The first element is 2 and the last element is also 2.[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:
[3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.[3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.[3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.[3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.[3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.[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 <= 1051 <= nums[i] <= 109Problem 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.
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.
Python
C
Java
C#
JavaScript
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.
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.
Python
C
Java
C#
JavaScript
Time Complexity: O(n), as we iterate through the array once.
Space Complexity: O(1), constant space is required.
| Approach | Complexity |
|---|---|
| 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. |
| Optimized Counting Using Sliding Window | Time Complexity: O(n), as we iterate through the array once. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2) | O(1) | Useful for understanding the condition and validating correctness on small arrays |
| Monotonic Stack Counting | O(n) | O(n) | Best general solution for large inputs; leverages decreasing stack and equal-value counting |
3113. Find the Number of Subarrays Where Boundary Elements Are Maximum | Binary Search | Monotonic • Aryan Mittal • 4,175 views views
Watch 9 more video solutions →Practice Find the Number of Subarrays Where Boundary Elements Are Maximum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor