Steps to Make Array Non-decreasing

You are given a 0-indexed integer array nums. In one step, remove all elements nums[i] where nums[i - 1] > nums[i] for all 0 < i < nums.length.

Return the number of steps performed until nums becomes a non-decreasing array.

Example 1:

Input: nums = [5,3,4,4,7,3,6,11,8,5,11]
Output: 3
Explanation: The following are the steps performed:
- Step 1: [5,**3**,4,4,7,**3**,6,11,**8**,**5**,11] becomes [5,4,4,7,6,11,11]
- Step 2: [5,**4**,4,7,**6**,11,11] becomes [5,4,7,11,11]
- Step 3: [5,**4**,7,11,11] becomes [5,7,11,11]
[5,7,11,11] is a non-decreasing array. Therefore, we return 3.

Example 2:

Input: nums = [4,5,7,7,13]
Output: 0
Explanation: nums is already a non-decreasing array. Therefore, we return 0.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

def steps_to_non_decreasing(nums):
    """Calculates the number of steps to make an array non-decreasing.

    Args:
        nums: A list of integers.

    Returns:
        The number of steps.
    """

    steps = 0
    while True:
        removed = False
        new_nums = [nums[0]]  # Always keep the first element
        for i in range(1, len(nums)):
            if nums[i - 1] <= nums[i]:
                new_nums.append(nums[i])
            else:
                removed = True
        nums = new_nums
        if not removed:
            break
        steps += 1
    return steps

# Example Usage:
nums1 = [5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11]
print(f"Input: {nums1}, Output: {steps_to_non_decreasing(nums1)}")  # Output: 3

nums2 = [4, 5, 7, 7, 13]
print(f"Input: {nums2}, Output: {steps_to_non_decreasing(nums2)}")  # Output: 0

nums3 = [10, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5]
print(f"Input: {nums3}, Output: {steps_to_non_decreasing(nums3)}") # Output: 1

nums4 = [5, 4, 3, 2, 1]
print(f"Input: {nums4}, Output: {steps_to_non_decreasing(nums4)}") # Output: 1

Explanation:

The problem requires us to find the number of steps needed to transform a given array into a non-decreasing array. In each step, we remove elements nums[i] where nums[i - 1] > nums[i]. The process continues until no more elements can be removed, meaning the array is non-decreasing.

Algorithm:

1. Initialization: Initialize a counter steps to 0. This variable will keep track of the number of removal steps performed.
2. Iteration: Repeat the following steps until no more elements are removed in a single step:
   • Set removed flag to False at the beginning of each step. This flag indicates whether any element has been removed in the current step.
   • Create a new array new_nums which initially contains only the first element of the input array nums.
   • Iterate through the nums array from the second element (index 1) to the last element.
   • For each element nums[i], compare it with the previous element nums[i - 1].
     • If nums[i - 1] <= nums[i], it means the current element does not violate the non-decreasing order, so append it to new_nums.
     • If nums[i - 1] > nums[i], it means the current element violates the non-decreasing order. Set the removed flag to True and do not append the current element to new_nums.
   • After iterating through all elements of nums, update nums with new_nums. This effectively removes all elements that violate the non-decreasing order in the current step.
   • If removed is False, it means no elements were removed in this step, so the array is now non-decreasing. Break the loop.
   • If removed is True, increment the steps counter.
3. Return: After the loop finishes, return the steps counter, which represents the number of steps performed to make the array non-decreasing.

Naive Solution:

The code provided above is already an efficient and straightforward solution to the problem. A more "naive" approach would involve creating a copy of the array in each iteration, which would increase the space complexity. However, the fundamental logic remains the same.

Big(O) Run-time Analysis:

The time complexity of the algorithm is O(NK), where N is the length of the input array nums and K is the number of steps required to make the array non-decreasing. In the worst-case scenario, K could be equal to N (e.g., when the array is strictly decreasing). In each step, we iterate through the array once. Therefore, the overall time complexity is O(NK).

Big(O) Space Usage Analysis:

The space complexity of the algorithm is O(N), where N is the length of the input array nums. This is because we create a new array new_nums in each step, which, in the worst case, can be of the same size as the input array. In the best case where only a few elements are removed, the space complexity would still be proportional to the remaining elements, making it O(N).

Edge Cases:

• Empty Array: If the input array is empty, the algorithm should return 0, as an empty array is considered non-decreasing.
• Already Non-decreasing Array: If the input array is already non-decreasing, the algorithm should return 0, as no steps are needed.
• Array with Duplicate Elements: The algorithm should correctly handle arrays with duplicate elements, treating them according to the non-decreasing order.
• Large Input Array: The algorithm should be able to handle large input arrays efficiently, with the time complexity being O(N*K). Due to the constraints, the array has at most 10^5 elements, therefore, it shouldn't result in Memory Limit Exceeded or Time Limit Exceeded errors.