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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Steps to Make Array Non-decreasing

Number: 2374

Difficulty: Medium

Paid? No

Companies: Amazon, Meta

Problem Description

Given a 0-indexed integer array nums, you must repeatedly remove all elements nums[i] where nums[i-1] > nums[i] in a single step (i.e. removal is done in parallel). The process is repeated until the array becomes non-decreasing. Return the number of steps required.

Key Insights

  • The removal operation is analogous to the "Poisonous Plants" problem where an element “dies” if its immediate left neighbor is larger.
  • Instead of simulating each step, we can compute for each element the number of steps (or "days") it will survive before being removed.
  • A monotonic stack can efficiently track the history of elements. Each element in the stack stores its value and the number of steps it takes for that element to be removed.
  • The maximum removal step among all elements will be the answer.

Space and Time Complexity

Time Complexity: O(n) – Each element is pushed and popped at most once from the stack. Space Complexity: O(n) – In the worst-case scenario where the array is non-decreasing, the stack stores all elements.

Solution

We use a monotonic stack where each entry is a pair (value, removalSteps). As we traverse through nums:

  • For the current number, set currentSteps to 0.
  • While the stack is non-empty and the value at the top of the stack is greater than the current number (indicating these elements will “cause” the removal):
    • Update currentSteps to be the maximum of its current value and the removal steps of the popped elements.
    • Pop the element from the stack.
  • If the stack is empty, then the current element will never be removed (set currentSteps to 0). Otherwise, if any element(s) were removed (currentSteps > 0), then the current element will be removed one step later (increment currentSteps by 1).
  • Track the maximum removal steps seen; this value is the number of steps required to obtain a non-decreasing array. The key trick is to count the "days" until removal without simulating the entire process, reducing the problem to a single pass using a stack.

Code Solutions

# Python solution using a monotonic stack
def totalSteps(nums):
    # Stack will store tuples: (number value, steps until removal)
    stack = []
    max_steps = 0  # result for the maximum steps required

    # Iterate over each number in the array
    for num in nums:
        current_steps = 0
        # While there's an element that is greater than the current number,
        # it means that element would trigger the removal of later elements.
        while stack and stack[-1][0] > num:
            # update current_steps to the max removal steps seen from elements that are popped
            current_steps = max(current_steps, stack[-1][1])
            stack.pop()
        # If stack is empty, current element is safe and won't be removed (set step to 0)
        # Otherwise, if any element was popped, current element needs one extra step.
        if not stack:
            current_steps = 0
        elif current_steps > 0:
            current_steps += 1
        # Update the global maximum result
        max_steps = max(max_steps, current_steps)
        # Push the current element and the corresponding removal steps into the stack
        stack.append((num, current_steps))
    return max_steps

# Example usage:
nums = [5,3,4,4,7,3,6,11,8,5,11]
print(totalSteps(nums))  # Output should be 3
← Back to All Questions