Jobs

Interviews

Discussions

Steps to Make Array Non-decreasing

Medium

Amazon

2 views

Topics:

ArraysStacks

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.

For example:

Example 1:

Input: nums = [5,3,4,4,7,3,6,11,8,5,11] Output: 3

Explanation:

- 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

Steps to Make Array Non-decreasing

Medium

Amazon

2 views

Topics:

ArraysStacks

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.

For example:

Example 1:

Input: nums = [5,3,4,4,7,3,6,11,8,5,11] Output: 3

Explanation:

- 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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type of the elements in the array, and what is the range of possible values for these elements? Can I assume they are integers?
Can the input array be empty, or can it contain null values? What should I return in these cases?
What does it mean to 'make an array non-decreasing'? Is it sufficient to make the array weakly increasing (i.e., each element is greater than or equal to the previous), or does it need to be strictly increasing?
What is the intended output? Should I return the minimum number of steps required, or the specific steps to take (e.g., the indices of the elements to modify)?
If there are multiple ways to make the array non-decreasing with the minimum number of steps, is any one of them acceptable, or is there a specific order or preference for the steps taken?

Brute Force Solution

Approach

Let's say we have a list of numbers and we want to make them go from smallest to largest, left to right. The brute force approach is to try every single possible thing we could change about the numbers until we find one that works. It's like trying every combination of locks on a safe until it opens.

Here's how the algorithm would work step-by-step:

Look at the first number, and compare it to the one next to it.
If the first number is bigger than the second number, try increasing the second number to be the same as the first.
Or, try decreasing the first number to be the same as the second.
See which one takes fewer changes.
Do this for every pair of numbers next to each other in the list.
Write down how many changes it took to make each pair 'good'.
Try a different set of changes than the previous one and repeat the process.
Keep track of all the possible ways to make the numbers go from smallest to largest.
Pick the option with the fewest total changes.

Code Implementation

def steps_to_make_array_non_decreasing_brute_force(numbers):
    minimum_changes = float('inf')
    
    def calculate_changes(current_numbers):
        changes = 0
        for index in range(len(current_numbers) - 1):
            if current_numbers[index] > current_numbers[index + 1]:
                #We need to consider two possibilities, increasing the right or decreasing the left.
                increase_right = list(current_numbers)
                increase_right[index + 1] = current_numbers[index]
                changes_increase = abs(current_numbers[index + 1] - increase_right[index + 1])

                decrease_left = list(current_numbers)
                decrease_left[index] = current_numbers[index + 1]
                changes_decrease = abs(current_numbers[index] - decrease_left[index])

                if changes_increase <= changes_decrease:
                    current_numbers[index + 1] = current_numbers[index]
                    changes += changes_increase
                else:
                    current_numbers[index] = current_numbers[index + 1]
                    changes += changes_decrease
        return changes

    import itertools
    
    # Generate all possible permutations is not right. The brute force approach is to try increase or decrease.
    # The core logic is to try increase or decrease only when current value > next value
    number_of_elements = len(numbers)
    
    # Create a list of possible changes to apply.
    possible_modifications = []

    def find_non_decreasing_count(index, current_numbers, changes_count):
        nonlocal minimum_changes
        if index == number_of_elements -1 :
            minimum_changes = min(minimum_changes, changes_count)
            return

        if current_numbers[index] <= current_numbers[index+1]:
            find_non_decreasing_count(index+1, current_numbers, changes_count)
            return
        
        # Two options, increase the right value or decrease the left
        increase_right_numbers = list(current_numbers)
        increase_right_numbers[index+1] = current_numbers[index]
        increase_right_changes_count = changes_count + abs(current_numbers[index+1] - current_numbers[index])
        find_non_decreasing_count(index+1, increase_right_numbers, increase_right_changes_count)

        decrease_left_numbers = list(current_numbers)
        decrease_left_numbers[index] = current_numbers[index+1]

        # Decrement the left element
        decrease_left_changes_count = changes_count + abs(current_numbers[index] - current_numbers[index+1])
        find_non_decreasing_count(index+1, decrease_left_numbers, decrease_left_changes_count)

    find_non_decreasing_count(0, numbers, 0)

    return minimum_changes

Big(O) Analysis

Time Complexity

O(n!) – The described brute force approach considers all possible ways to modify the array elements to achieve a non-decreasing order. For each pair of adjacent elements, there are multiple choices: increase the second element, decrease the first element, or potentially leave them unchanged. The total number of such possibilities explodes factorially as the array size 'n' grows because we are essentially exploring every possible combination of modifications. Therefore, the number of operations grows proportional to n!, leading to a time complexity of O(n!).

Space Complexity

O(N!) – The brute force approach, as described, explores all possible combinations of increasing or decreasing each element. This implies an implicit branching tree where each element's modification represents a level, and at each level, we explore multiple options (incrementing or decrementing a number). Since the algorithm needs to keep track of all possible sets of changes, it implicitly stores these combinations. In the worst-case, every element might need to be modified resulting in considering all the combinations for N elements, leading to a space complexity proportional to O(branches^depth) where 'branches' is roughly 2 (increase or decrease) for each node. Therefore, the space complexity becomes factorial O(N!), because it must explore almost all possible permutations of modifications.

Optimal Solution

Approach

We want to find the minimum number of steps to make an array non-decreasing. The key idea is to use a stack to keep track of potential elements that might need to be removed, and to understand when an element definitely needs to be removed to maintain the non-decreasing property.

Here's how the algorithm would work step-by-step:

Imagine you're looking at the array from left to right, one number at a time.
Think of a stack of plates, where you can only add or remove plates from the top.
As you go through the numbers, add each one to your stack.
However, before adding, check if the number at the top of the stack is bigger than the one you are considering.
If it is, this means we will eventually need to remove the bigger numbers from the stack to keep the array non-decreasing. Start counting steps for those removals.
Keep removing and counting until the top of the stack is not bigger, or the stack is empty.
Add the current number to the stack.
The largest step count that any number in the stack experienced tells you the minimum number of steps required to make the whole array non-decreasing.
This works because it identifies exactly which numbers need to be removed and ensures you're only counting the necessary removals based on how they affect later numbers.

Code Implementation

def steps_to_make_array_non_decreasing(numbers):
    stack = []
    max_steps = 0

    for number in numbers:
        steps = 0

        # Remove elements that violate non-decreasing order
        while stack and stack[-1][0] > number:
            steps = max(steps, stack[-1][1] + 1)
            stack.pop()

        stack.append((number, steps))
        max_steps = max(max_steps, steps)

    return max_steps

Big(O) Analysis

Time Complexity

O(n) – We iterate through the input array of size n once. In the inner while loop, elements are pushed onto and popped from the stack. Each element is pushed onto the stack once and popped at most once. Thus, the while loop executes at most n times across the entire algorithm. Therefore, the overall time complexity is O(n).

Space Complexity

O(N) – The provided solution uses a stack to store elements of the array. In the worst-case scenario, where the input array is monotonically decreasing, all N elements will be pushed onto the stack before any elements are popped. The stack also stores the step count for each element which is at most N. Therefore, the auxiliary space used by the algorithm is proportional to the size of the input array, N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty as no operations are needed.
Array with only one element	Return 0 since a single-element array is already non-decreasing.
Array already sorted in non-decreasing order	Return 0 as no steps are required to make it non-decreasing.
Array sorted in strictly decreasing order	Requires maximum number of steps, should still be handled efficiently by the algorithm.
Array with all elements equal	Return 0 as it is already non-decreasing.
Array containing very large numbers (potential for integer overflow)	Use appropriate data types (e.g., long) to prevent overflow during calculations when modifying elements, or modular arithmetic when the prompt specifies a module.
Large input array (performance considerations)	Ensure the algorithm has optimal time complexity, such as O(n) or O(n log n), to handle large inputs efficiently; avoid O(n^2) or higher complexities.
Array containing negative numbers and zeros	The algorithm should correctly handle negative numbers and zeros without any special modifications, assuming the comparison logic uses <=.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type of the elements in the array, and what is the range of possible values for these elements? Can I assume they are integers?
Can the input array be empty, or can it contain null values? What should I return in these cases?
What does it mean to 'make an array non-decreasing'? Is it sufficient to make the array weakly increasing (i.e., each element is greater than or equal to the previous), or does it need to be strictly increasing?
What is the intended output? Should I return the minimum number of steps required, or the specific steps to take (e.g., the indices of the elements to modify)?
If there are multiple ways to make the array non-decreasing with the minimum number of steps, is any one of them acceptable, or is there a specific order or preference for the steps taken?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Look at the first number, and compare it to the one next to it.
If the first number is bigger than the second number, try increasing the second number to be the same as the first.
Or, try decreasing the first number to be the same as the second.
See which one takes fewer changes.
Do this for every pair of numbers next to each other in the list.
Write down how many changes it took to make each pair 'good'.
Try a different set of changes than the previous one and repeat the process.
Keep track of all the possible ways to make the numbers go from smallest to largest.
Pick the option with the fewest total changes.

Code Implementation

def steps_to_make_array_non_decreasing_brute_force(numbers):
    minimum_changes = float('inf')
    
    def calculate_changes(current_numbers):
        changes = 0
        for index in range(len(current_numbers) - 1):
            if current_numbers[index] > current_numbers[index + 1]:
                #We need to consider two possibilities, increasing the right or decreasing the left.
                increase_right = list(current_numbers)
                increase_right[index + 1] = current_numbers[index]
                changes_increase = abs(current_numbers[index + 1] - increase_right[index + 1])

                decrease_left = list(current_numbers)
                decrease_left[index] = current_numbers[index + 1]
                changes_decrease = abs(current_numbers[index] - decrease_left[index])

                if changes_increase <= changes_decrease:
                    current_numbers[index + 1] = current_numbers[index]
                    changes += changes_increase
                else:
                    current_numbers[index] = current_numbers[index + 1]
                    changes += changes_decrease
        return changes

    import itertools
    
    # Generate all possible permutations is not right. The brute force approach is to try increase or decrease.
    # The core logic is to try increase or decrease only when current value > next value
    number_of_elements = len(numbers)
    
    # Create a list of possible changes to apply.
    possible_modifications = []

    def find_non_decreasing_count(index, current_numbers, changes_count):
        nonlocal minimum_changes
        if index == number_of_elements -1 :
            minimum_changes = min(minimum_changes, changes_count)
            return

        if current_numbers[index] <= current_numbers[index+1]:
            find_non_decreasing_count(index+1, current_numbers, changes_count)
            return
        
        # Two options, increase the right value or decrease the left
        increase_right_numbers = list(current_numbers)
        increase_right_numbers[index+1] = current_numbers[index]
        increase_right_changes_count = changes_count + abs(current_numbers[index+1] - current_numbers[index])
        find_non_decreasing_count(index+1, increase_right_numbers, increase_right_changes_count)

        decrease_left_numbers = list(current_numbers)
        decrease_left_numbers[index] = current_numbers[index+1]

        # Decrement the left element
        decrease_left_changes_count = changes_count + abs(current_numbers[index] - current_numbers[index+1])
        find_non_decreasing_count(index+1, decrease_left_numbers, decrease_left_changes_count)

    find_non_decreasing_count(0, numbers, 0)

    return minimum_changes

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you're looking at the array from left to right, one number at a time.
Think of a stack of plates, where you can only add or remove plates from the top.
As you go through the numbers, add each one to your stack.
However, before adding, check if the number at the top of the stack is bigger than the one you are considering.
If it is, this means we will eventually need to remove the bigger numbers from the stack to keep the array non-decreasing. Start counting steps for those removals.
Keep removing and counting until the top of the stack is not bigger, or the stack is empty.
Add the current number to the stack.
The largest step count that any number in the stack experienced tells you the minimum number of steps required to make the whole array non-decreasing.
This works because it identifies exactly which numbers need to be removed and ensures you're only counting the necessary removals based on how they affect later numbers.

Code Implementation

def steps_to_make_array_non_decreasing(numbers):
    stack = []
    max_steps = 0

    for number in numbers:
        steps = 0

        # Remove elements that violate non-decreasing order
        while stack and stack[-1][0] > number:
            steps = max(steps, stack[-1][1] + 1)
            stack.pop()

        stack.append((number, steps))
        max_steps = max(max_steps, steps)

    return max_steps

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty as no operations are needed.
Array with only one element	Return 0 since a single-element array is already non-decreasing.
Array already sorted in non-decreasing order	Return 0 as no steps are required to make it non-decreasing.
Array sorted in strictly decreasing order	Requires maximum number of steps, should still be handled efficiently by the algorithm.
Array with all elements equal	Return 0 as it is already non-decreasing.
Array containing very large numbers (potential for integer overflow)	Use appropriate data types (e.g., long) to prevent overflow during calculations when modifying elements, or modular arithmetic when the prompt specifies a module.
Large input array (performance considerations)	Ensure the algorithm has optimal time complexity, such as O(n) or O(n log n), to handle large inputs efficiently; avoid O(n^2) or higher complexities.
Array containing negative numbers and zeros	The algorithm should correctly handle negative numbers and zeros without any special modifications, assuming the comparison logic uses <=.