Find the Number of Subarrays Where Boundary Elements Are Maximum - Video Solutions

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.