Maximal Range That Each Element Is Maximum in It — LeetCode 2832 Python Solution
MediumLeetCode PremiumStackArrayMonotonic Stack
- Problem
- #2832
- Pattern
- Stack
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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].
Example
- 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.
Python solution
Python
class Solution:
def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:
n = len(nums)
left = [-1] * n
right = [n] * n
stk = []
for i, x in enumerate(nums):
while stk and nums[stk[-1]] <= x:
stk.pop()
if stk:
left[i] = stk[-1]
stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
while stk and nums[stk[-1]] <= nums[i]:
stk.pop()
if stk:
right[i] = stk[-1]
stk.append(i)
return [r - l - 1 for l, r in zip(left, right)]Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 2832. Maximal Range That Each Element Is Maximum in It is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2832. Maximal Range That Each Element Is Maximum in It?
- LeetCode 2832. Maximal Range That Each Element Is Maximum in It is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2832. Maximal Range That Each Element Is Maximum in It?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2832. Maximal Range That Each Element Is Maximum in It?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2832. Maximal Range That Each Element Is Maximum in It cover?
- LeetCode 2832. Maximal Range That Each Element Is Maximum in It is tagged Stack, Array and Monotonic Stack on LeetCode.
- Is LeetCode 2832. Maximal Range That Each Element Is Maximum in It a premium problem?
- Yes. LeetCode 2832. Maximal Range That Each Element Is Maximum in It is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.