Is Maximal Range That Each Element Is Maximum in It easy or hard?

The problem is usually classified as Medium difficulty. The challenge is recognizing that each element’s valid range is defined by the nearest greater elements, which naturally leads to a monotonic stack solution.

Maximal Range That Each Element Is Maximum in It Python/Java solution

The typical implementation maintains a stack of indices while iterating through the array. When a larger element appears, smaller elements are popped and their right boundary is recorded. The same logic works in Python, Java, C++, Go, and TypeScript with identical O(n) complexity.

How to solve Maximal Range That Each Element Is Maximum in It in O(n)?

Compute the nearest greater element on both sides using a monotonic decreasing stack. During traversal, pop elements when a larger value appears and record the right boundary. A reverse pass or separate stack computation finds the left boundary. The maximum valid range for each index is between these two boundaries.

What is the best approach for Maximal Range That Each Element Is Maximum in It?

The most efficient approach uses a monotonic decreasing stack to find the nearest greater element on both the left and right of every index. These boundaries determine how far each element can extend while remaining the maximum. The algorithm runs in O(n) time and O(n) space because each element is pushed and popped from the stack at most once.

Is Maximal Range That Each Element Is Maximum in It asked at Google/Amazon/Meta?

Problems based on monotonic stacks and nearest greater elements frequently appear in interviews at companies like Amazon, Google, and Meta. Variants such as Largest Rectangle in Histogram and Sum of Subarray Minimums test the same core technique used in this problem.

What data structure is used in Maximal Range That Each Element Is Maximum in It?

The key data structure is a monotonic stack that stores array indices in decreasing order of values. This structure helps efficiently determine previous and next greater elements without scanning the array repeatedly.

What is the time complexity of Maximal Range That Each Element Is Maximum in It?

The optimal monotonic stack solution runs in O(n) time with O(n) extra space. Each element is processed once when pushed to the stack and once when popped. A brute force method that expands left and right for every element takes O(n²) time.

Description Hints 6 Solution Video 12:51

2832. Maximal Range That Each Element Is Maximum in It

Medium75.5% acceptance1 companyPremium elsewhere, free here

You are given a 0-indexed array nums of distinct integers.

Let us define a 0-indexed array ans of the same length as nums in the following way:

ans[i] is the maximum length of a subarray nums[l..r], such that the maximum element in that subarray is equal to nums[i].

Return the array ans.

Note that a subarray is a contiguous part of the array.

Example 1:

Input: nums = [1,5,4,3,6]
Output: [1,4,2,1,5]
Explanation: For nums[0] the longest subarray in which 1 is the maximum is nums[0..0] so ans[0] = 1.
For nums[1] the longest subarray in which 5 is the maximum is nums[0..3] so ans[1] = 4.
For nums[2] the longest subarray in which 4 is the maximum is nums[2..3] so ans[2] = 2.
For nums[3] the longest subarray in which 3 is the maximum is nums[3..3] so ans[3] = 1.
For nums[4] the longest subarray in which 6 is the maximum is nums[0..4] so ans[4] = 5.

Example 2:

Input: nums = [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: For nums[i] the longest subarray in which it's the maximum is nums[0..i] so ans[i] = i + 1.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
All elements in nums are distinct.

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

For each index, we must find the nearest bigger element on both its left and right sides.

Hint 2

First, find the nearest bigger element on the left side of each element. To do that, use a stack of pairs (value, index).

Hint 3

Start iterating from the beginning of the array.

Hint 4

Whenever we reach an element nums[index], while the top of the stack is smaller than nums[index], we pop from the stack.

Hint 5

If there is an element left in the stack, top.index + 1 would be the answer. Otherwise, 0 is the answer.

Hint 6

After that, we push (nums[index], index) to the stack and go for the next element.

12:51

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,5,4,3,6]

Input

[1,2,3,4,5]

Your code is saved on this device.Solution