Maximal Range That Each Element Is Maximum in It

Maximal Range That Each Element Is Maximum in It

What is this problem about?

In this problem, you are given an array of integers. For every element in the array, you must find the size of the maximum contiguous subarray (or "range") where that specific element is the absolute maximum value. The problem usually asks you to return an array of these range sizes corresponding to each element.

Why is this asked in interviews?

This problem is a direct inversion of the classic "Largest Rectangle in Histogram" problem. Instead of expanding until you hit a smaller element, you expand until you hit a larger element. It is the purest test of a candidate's mastery of the Monotonic Stack. Interviewers ask it to evaluate if you understand how stacks can efficiently calculate boundaries in $O(N)$ time.

Algorithmic pattern used

This problem is solved optimally using a Monotonic Decreasing Stack. For each element, its valid range extends to the left until it hits a strictly larger number, and to the right until it hits a strictly larger number.

1. Traverse left-to-right with a stack to find the Next Greater Element index for each item.
2. Traverse right-to-left with a stack to find the Previous Greater Element index for each item.
3. The valid range size for an element at index i is Right_Index - Left_Index - 1.

Example explanation

Array: [1, 5, 4, 3, 6] Let's find the boundaries.

• For 1 (idx 0): Left boundary = -1. Next greater is 5 (idx 1). Range = 1 - (-1) - 1 = 1.
• For 5 (idx 1): Left greater = -1. Next greater is 6 (idx 4). Range = 4 - (-1) - 1 = 4 (subarray [1, 5, 4, 3]).
• For 4 (idx 2): Left greater is 5 (idx 1). Next greater is 6 (idx 4). Range = 4 - 1 - 1 = 2 (subarray [4, 3]).
• For 6 (idx 4): Left greater = -1. Next greater = 5 (end of array). Range = 5 - (-1) - 1 = 5 (whole array).

Common mistakes candidates make

A major pitfall is improperly handling duplicate numbers. If the array is [4, 4], and both stop at a "greater than or equal to" condition, they will limit each other, creating artificially small ranges. The rule of thumb for monotonic stacks handling duplicates is: use strictly greater (>) for one direction, and greater-or-equal (>=) for the other. This prevents overlap logic from miscalculating boundaries.

Interview preparation tip

When studying the Maximal Range pattern, visualize the Monotonic Stack as a line of sight. An element looks left until a taller building blocks its view, and looks right until a taller building blocks its view. The distance between those two blocking buildings is its domain. Memorize the two-pass stack template; it solves dozens of advanced array boundary problems.