We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximal Range That Each Element Is Maximum in It

Number: 3088

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given a 0-indexed array of distinct integers, nums, for each element nums[i] find the maximum length of a contiguous subarray in which nums[i] is the maximum element. Return an array ans where ans[i] represents that maximum length.

Key Insights

  • For each element, determine how far you can extend to the left and right until encountering a number greater than the current element.
  • Using a monotonic stack helps efficiently find the previous and next greater elements.
  • The desired subarray for element nums[i] extends from (previous greater element + 1) to (next greater element - 1).
  • Since all elements are distinct, the comparison is straightforward and each element will act as a unique maximum within its extendable range.

Space and Time Complexity

Time Complexity: O(n) – Each element is pushed and popped at most once onto the stack. Space Complexity: O(n) – Extra space is used for the left/right boundary arrays and the stacks.

Solution

We can solve the problem by determining for each index i the farthest indices to which we can expand while ensuring nums[i] remains the maximum in that subarray. This can be done by finding:

  1. The nearest index to the left where the element is greater than nums[i] (or the array boundary if none exists).
  2. The nearest index to the right where the element is greater than nums[i] (or the array boundary if none exists).

We use two monotonic stacks:

  • One to traverse from left-to-right to compute left boundaries.
  • One to traverse from right-to-left to compute right boundaries.

Then, compute the maximal subarray length for nums[i] using: ans[i] = right[i] - left[i] + 1

This algorithm efficiently determines the answer for each element in one pass for left boundaries and one pass for right boundaries, ensuring O(n) time complexity.

Code Solutions

# Python Solution
def maximalRange(nums):
    n = len(nums)
    ans = [0] * n
    left_bound = [0] * n   # stores the left boundary for each element
    right_bound = [0] * n  # stores the right boundary for each element

    # Compute left boundaries using a monotonic decreasing stack
    stack = []
    for i in range(n):
        # Pop until the stack is empty or the element at the top is greater than current
        while stack and nums[stack[-1]] < nums[i]:
            stack.pop()
        # If stack is empty, no previous greater element exists
        left_bound[i] = 0 if not stack else stack[-1] + 1
        stack.append(i)

    # Clear the stack to compute right boundaries
    stack = []
    for i in range(n-1, -1, -1):
        # Pop until the stack is empty or the element at the top is greater than current
        while stack and nums[stack[-1]] < nums[i]:
            stack.pop()
        # If stack is empty, no next greater element exists
        right_bound[i] = n - 1 if not stack else stack[-1] - 1
        stack.append(i)

    # Compute answer for each element: length of subarray = right_bound[i] - left_bound[i] + 1
    for i in range(n):
        ans[i] = right_bound[i] - left_bound[i] + 1

    return ans

# Example usage:
nums = [1,5,4,3,6]
print(maximalRange(nums))  # Expected output: [1,4,2,1,5]
← Back to All Questions