Problem Description

You have an array nums containing distinct integers at different positions (0-indexed). Your task is to create a new array ans where each element represents a specific measurement related to subarrays.

For each position i in the array, you need to find the maximum possible length of any subarray where nums[i] is the largest element in that subarray. This means you're looking for the longest contiguous sequence of elements where nums[i] remains the maximum value.

For example, if you have nums = [1, 5, 4, 3, 6]:

• For nums[0] = 1: The longest subarray where 1 is the maximum is just [1] itself, so length is 1
• For nums[1] = 5: The longest subarray where 5 is the maximum could be [1, 5, 4, 3], so length is 4
• For nums[2] = 4: The longest subarray where 4 is the maximum could be [4, 3], so length is 2
• And so on...

The solution uses a monotonic stack approach to efficiently find, for each element:

• left[i]: The position of the nearest element to the left that is greater than nums[i]
• right[i]: The position of the nearest element to the right that is greater than nums[i]

Once these boundaries are found, the maximum length of a subarray where nums[i] is the maximum element is simply right[i] - left[i] - 1. This works because any subarray containing elements between these boundaries (exclusive) will have nums[i] as its maximum value.

The algorithm processes the array twice with a stack - once from left to right to find left boundaries, and once from right to left to find right boundaries. Elements are popped from the stack when they are smaller than or equal to the current element, ensuring the stack maintains elements in decreasing order.

Intuition

The key insight is to think about when an element nums[i] can be the maximum of a subarray. For nums[i] to be the maximum, all elements in that subarray must be less than or equal to nums[i].

This means we need to find how far we can extend to the left and right from position i while keeping nums[i] as the largest element. The extension stops when we encounter an element larger than nums[i] in either direction.

So the problem transforms into finding, for each element:

• The first element greater than nums[i] to its left
• The first element greater than nums[i] to its right

The region between these two boundaries (exclusive) gives us the maximum range where nums[i] can serve as the maximum element.

Why use a monotonic stack? When we traverse the array, we want to efficiently track potential boundaries. A decreasing monotonic stack helps because:

• When we encounter a new element, any smaller elements in the stack cannot be boundaries for future elements
• The stack maintains only the "relevant" larger elements that could serve as boundaries
• Each element is pushed and popped at most once, giving us O(n) time complexity

For example, if we're moving left to right and maintain a decreasing stack, when we see element nums[i]:

• We pop all elements ≤ nums[i] from the stack (they can't be left boundaries for nums[i])
• The top of the stack (if it exists) is the nearest larger element to the left
• We then add nums[i] to the stack for future elements

This approach elegantly solves what would otherwise require O(n²) time (checking all possible subarrays) in just O(n) time with two passes.

Learn more about Stack and Monotonic Stack patterns.

Solution Approach

The solution uses a monotonic stack pattern to find boundaries for each element. Here's the step-by-step implementation:

1. Initialize Data Structures:

• Create left array initialized with -1 (representing no left boundary)
• Create right array initialized with n (representing no right boundary)
• Use an empty stack stk to maintain indices of elements

2. First Pass - Find Left Boundaries:

for i, x in enumerate(nums):
    while stk and nums[stk[-1]] <= x:
        stk.pop()
    if stk:
        left[i] = stk[-1]
    stk.append(i)

• Traverse from left to right
• For each element nums[i], pop all elements from stack that are ≤ nums[i]
• After popping, the top of stack (if exists) is the index of the nearest larger element to the left
• Push current index i to stack for future elements

3. Second Pass - Find Right Boundaries:

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)

• Clear the stack and traverse from right to left
• Apply the same logic: pop elements ≤ nums[i]
• The top of stack after popping gives the nearest larger element to the right

4. Calculate Results:

return [r - l - 1 for l, r in zip(left, right)]

• For each position i, the maximum subarray length where nums[i] is the maximum is right[i] - left[i] - 1
• This formula works because:
  • left[i] is the index of the first larger element to the left (exclusive boundary)
  • right[i] is the index of the first larger element to the right (exclusive boundary)
  • The valid range is (left[i], right[i]) exclusive, so the length is right[i] - left[i] - 1

Time Complexity: O(n) - Each element is pushed and popped at most once in each pass Space Complexity: O(n) - For the left, right arrays and stack

Example Walkthrough

Let's walk through the algorithm with nums = [3, 1, 5, 2].

Goal: For each element, find the maximum length of a subarray where that element is the largest.

Step 1: Find Left Boundaries We traverse left to right with a stack to find the nearest larger element to the left of each position.

• i=0, nums[0]=3: Stack is empty. No larger element to the left, so left[0] = -1. Push index 0 to stack. Stack: [0]

• i=1, nums[1]=1: Stack has [0]. Since nums[0]=3 > 1, don't pop. The nearest larger element to the left is at index 0, so left[1] = 0. Push index 1 to stack. Stack: [0, 1]

• i=2, nums[2]=5: Stack has [0, 1]. Pop index 1 because nums[1]=1 ≤ 5. Pop index 0 because nums[0]=3 ≤ 5. Stack is now empty. No larger element to the left, so left[2] = -1. Push index 2 to stack. Stack: [2]

• i=3, nums[3]=2: Stack has [2]. Since nums[2]=5 > 2, don't pop. The nearest larger element to the left is at index 2, so left[3] = 2. Push index 3 to stack. Stack: [2, 3]

Result: left = [-1, 0, -1, 2]

Step 2: Find Right Boundaries We traverse right to left with a stack to find the nearest larger element to the right of each position.

• i=3, nums[3]=2: Stack is empty. No larger element to the right, so right[3] = 4 (array length). Push index 3 to stack. Stack: [3]

• i=2, nums[2]=5: Stack has [3]. Pop index 3 because nums[3]=2 ≤ 5. Stack is now empty. No larger element to the right, so right[2] = 4. Push index 2 to stack. Stack: [2]

• i=1, nums[1]=1: Stack has [2]. Since nums[2]=5 > 1, don't pop. The nearest larger element to the right is at index 2, so right[1] = 2. Push index 1 to stack. Stack: [2, 1]

• i=0, nums[0]=3: Stack has [2, 1]. Pop index 1 because nums[1]=1 ≤ 3. Stack now has [2]. Since nums[2]=5 > 3, don't pop. The nearest larger element to the right is at index 2, so right[0] = 2. Push index 0 to stack. Stack: [2, 0]

Result: right = [2, 2, 4, 4]

Step 3: Calculate Maximum Subarray Lengths For each position i: ans[i] = right[i] - left[i] - 1

• ans[0] = 2 - (-1) - 1 = 2 → Subarray [3, 1] has max element 3, length 2
• ans[1] = 2 - 0 - 1 = 1 → Subarray [1] has max element 1, length 1
• ans[2] = 4 - (-1) - 1 = 4 → Subarray [3, 1, 5, 2] has max element 5, length 4
• ans[3] = 4 - 2 - 1 = 1 → Subarray [2] has max element 2, length 1

Final Answer: [2, 1, 4, 1]

Each value represents the maximum length of a subarray where the corresponding element is the largest value in that subarray.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the input array nums. Although there are two for loops that iterate through the array and within each loop there's a while loop for stack operations, each element is pushed and popped from the stack at most once. The first loop processes elements from left to right to find the nearest greater element on the left, and the second loop processes elements from right to left to find the nearest greater element on the right. Therefore, the total number of operations is linear with respect to n.

The space complexity is O(n). The algorithm uses three arrays (left, right, and the result array from the list comprehension) each of size n, and a stack stk that can contain at most n elements. Even though the stack is reused between the two loops, the overall space requirement is still O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Equal Elements

One of the most common mistakes is using strict inequality (<) instead of <= when popping elements from the stack.

Wrong Implementation:

while stack and nums[stack[-1]] < value:  # Wrong: using < instead of <=
    stack.pop()

Why this fails: If we only pop elements strictly less than the current value, equal elements would remain in the stack. This would incorrectly limit the range where the current element can be the maximum. For example, with nums = [3, 3, 3], each element should have a range length of 1 (only itself), but using < would give incorrect boundaries.

Correct Implementation:

while stack and nums[stack[-1]] <= value:  # Correct: using <=
    stack.pop()

2. Forgetting to Clear/Reset the Stack Between Passes

Another common mistake is reusing the same stack for both left and right boundary calculations without clearing it.

Wrong Implementation:

stack = []
# First pass for left boundaries
for i, x in enumerate(nums):
    # ... process left boundaries
  
# Forgot to clear stack!
# stack = []  # Missing this line
for i in range(n - 1, -1, -1):
    # ... process right boundaries with contaminated stack

Solution: Always reset the stack before the second pass:

stack = []  # Clear stack before right boundary calculation

3. Incorrect Boundary Initialization

Initializing boundaries incorrectly can lead to wrong range calculations.

Wrong Implementation:

left_boundary = [0] * n      # Wrong: should be -1
right_boundary = [n - 1] * n  # Wrong: should be n

Why this fails:

• If an element has no greater element to its left, its left boundary should be -1 (before index 0)
• If an element has no greater element to its right, its right boundary should be n (after index n-1)
• Using 0 and n-1 would incorrectly include actual array positions as boundaries

Correct Implementation:

left_boundary = [-1] * n   # Correct: -1 for no left boundary
right_boundary = [n] * n    # Correct: n for no right boundary

4. Off-by-One Error in Range Calculation

A subtle but critical error is forgetting the -1 in the final calculation.

Wrong Implementation:

return [right - left for left, right in zip(left_boundary, right_boundary)]  # Missing -1

Why this fails: The boundaries are exclusive (they point to elements greater than the current element), so the actual range is from left + 1 to right - 1 inclusive. The length is therefore (right - 1) - (left + 1) + 1 = right - left - 1.

Correct Implementation:

return [right - left - 1 for left, right in zip(left_boundary, right_boundary)]