Jobs

Interviews

Discussions

Make Array Non-decreasing or Non-increasing

Hard

Asked by:

30 views

Topics:

Dynamic ProgrammingArrays

You are given an integer array nums. You can perform the following operation on it any number of times:

Pick any element and either increase or decrease it by 1.

Return the minimum number of operations to make nums non-decreasing or non-increasing.

Example 1:

Input: nums = [3,2,1,2,1]
Output: 2
Explanation:
You can make nums non-decreasing with the following operations:
- Decrease nums[0] to 2.
- Increase nums[2] to 2.
You can make nums non-increasing with the following operations:
- Increase nums[1] to 3.
- Decrease nums[3] to 1.
The optimal way is to make the array non-decreasing with 2 operations.

Example 2:

Input: nums = [2,2,3,4]
Output: 0
Explanation: nums is already non-decreasing.

Example 3:

Input: nums = [5,4,3,2,1]
Output: 0
Explanation: nums is already non-increasing.

Constraints:

1 <= nums.length <= 2000
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

Make Array Non-decreasing or Non-increasing

Hard

Asked by:

30 views

Topics:

Dynamic ProgrammingArrays

You are given an integer array nums. You can perform the following operation on it any number of times:

Pick any element and either increase or decrease it by 1.

Return the minimum number of operations to make nums non-decreasing or non-increasing.

Example 1:

Input: nums = [3,2,1,2,1]
Output: 2
Explanation:
You can make nums non-decreasing with the following operations:
- Decrease nums[0] to 2.
- Increase nums[2] to 2.
You can make nums non-increasing with the following operations:
- Increase nums[1] to 3.
- Decrease nums[3] to 1.
The optimal way is to make the array non-decreasing with 2 operations.

Example 2:

Input: nums = [2,2,3,4]
Output: 0
Explanation: nums is already non-decreasing.

Example 3:

Input: nums = [5,4,3,2,1]
Output: 0
Explanation: nums is already non-increasing.

Constraints:

1 <= nums.length <= 2000
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

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 are the possible ranges and data types of the numbers in the input array? Should I expect integers, floats, or a mix? Can the numbers be negative, zero, or only positive?
Is it always possible to make the array either non-decreasing or non-increasing with the operations allowed, or are there cases where it's impossible? If it's impossible, what should I return?
What is the size limit of the input array? I want to be mindful of memory constraints.
If there are multiple ways to make the array non-decreasing or non-increasing, does it matter which solution I choose, or should I optimize for the minimal number of changes?
Can you provide some examples of input arrays and their corresponding solutions to better understand the expected output?

Brute Force Solution

Approach

The brute force approach involves trying every single possible change we can make to the list of numbers. We'll explore all ways to make the list non-decreasing and all ways to make the list non-increasing, and then choose the solution that requires the fewest changes.

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

First, let's consider making the list non-decreasing. That means each number should be the same or bigger than the one before it.
Try changing the first number to every possible value. For each of these changes, see how many more changes we need to make to the rest of the numbers to make the whole list non-decreasing.
Then, go back and try changing the second number to every possible value, and again see how many changes that would take to make the list non-decreasing.
Repeat this for every number in the list. This process will identify how many changes are needed to make the array non-decreasing.
Next, do the same thing, but try to make the list non-increasing instead. That means each number should be the same or smaller than the one before it. Repeat the above process.
Finally, compare the number of changes it took to make the list non-decreasing versus the number of changes it took to make the list non-increasing. Choose the option that required the fewest changes.

Code Implementation

def make_array_non_decreasing_or_non_increasing(numbers):
    def calculate_changes_non_decreasing(array):
        number_of_changes = 0
        for index in range(1, len(array)):
            if array[index] < array[index - 1]:
                number_of_changes += array[index - 1] - array[index]
                array[index] = array[index - 1]
        return number_of_changes

    def calculate_changes_non_increasing(array):
        number_of_changes = 0
        for index in range(1, len(array)):
            if array[index] > array[index - 1]:
                number_of_changes += array[index] - array[index - 1]
                array[index] = array[index - 1]
        return number_of_changes

    minimum_changes = float('inf')

    # Iterate to explore every possible value for each number
    for index_to_change in range(len(numbers)):
        original_value = numbers[index_to_change]

        # We try every number in the array
        for new_value in numbers:

            # Create copies to avoid modifying the original array
            non_decreasing_attempt = numbers[:]
            non_increasing_attempt = numbers[:]
            non_decreasing_attempt[index_to_change] = new_value
            non_increasing_attempt[index_to_change] = new_value

            changes_non_decreasing = calculate_changes_non_decreasing(non_decreasing_attempt)
            changes_non_increasing = calculate_changes_non_increasing(non_increasing_attempt)

            # Count changes needed for current iteration.
            current_changes = min(changes_non_decreasing, changes_non_increasing) + 1
            if new_value != original_value:
                current_changes -= 1
            
            minimum_changes = min(minimum_changes, current_changes)

    non_decreasing_numbers = numbers[:]
    non_increasing_numbers = numbers[:]

    non_decreasing_changes_initial = calculate_changes_non_decreasing(non_decreasing_numbers)
    non_increasing_changes_initial = calculate_changes_non_increasing(non_increasing_numbers)

    minimum_changes = min(minimum_changes, non_decreasing_changes_initial, non_increasing_changes_initial)

    return minimum_changes

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements in the input array. For each element, it considers changing its value and then iterates through the rest of the array to enforce either non-decreasing or non-increasing order. Therefore, for each of the n elements, we potentially perform another n operations. This results in approximately n * n total operations. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The provided brute force approach, as described, primarily involves iteratively changing elements of the input array and counting changes. It doesn't mention creating any auxiliary data structures like temporary arrays, hash maps, or sets to store intermediate states or visited values. The algorithm operates directly on the input array, making modifications and comparing counts. Therefore, the space complexity is dominated by a few constant variables (e.g., to keep track of change counts, the minimum number of changes so far), irrespective of the input array's size, N. This results in constant auxiliary space.

Optimal Solution

Approach

The goal is to minimize the changes needed to make a sequence either always going up or always going down. We do this by considering each number and deciding whether to keep it as is or change it to fit the increasing or decreasing pattern, and by only looking at previous decisions. This avoids trying every single combination, saving lots of effort.

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

Imagine you're building two staircases, one going up and one going down.
For each number, decide what it would cost to make it fit on the 'up' staircase and what it would cost to make it fit on the 'down' staircase, considering the previous stair step.
Keep track of the minimum cost for the 'up' staircase and the 'down' staircase as you go along.
At the end, the minimum cost of either the 'up' staircase or the 'down' staircase is your answer.
Essentially, you're making the best local decision at each number, knowing the optimal cost to get to that number.

Code Implementation

def min_changes(sequence):
    sequence_length = len(sequence)
    if sequence_length <= 1:
        return 0

    increasing_changes = [0] * sequence_length
    decreasing_changes = [0] * sequence_length

    for i in range(1, sequence_length):
        increasing_changes[i] = float('inf')
        decreasing_changes[i] = float('inf')

        for j in range(i):
            # Calculate changes to make increasing
            if sequence[i] >= sequence[j]:
                increasing_changes[i] = min(increasing_changes[i], increasing_changes[j])
            else:
                increasing_changes[i] = min(increasing_changes[i], increasing_changes[j] + 1)

            # Calculate changes to make decreasing
            if sequence[i] <= sequence[j]:
                decreasing_changes[i] = min(decreasing_changes[i], decreasing_changes[j])
            else:
                decreasing_changes[i] = min(decreasing_changes[i], decreasing_changes[j] + 1)

    # Return the minimum of the two change counts
    return min(increasing_changes[sequence_length - 1], decreasing_changes[sequence_length - 1])

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once. For each element, it performs a constant amount of work: calculating the cost to fit it into an increasing and decreasing sequence based on the previous optimal costs. There are no nested loops or recursive calls that depend on the input size. Therefore, the time complexity is directly proportional to the number of elements, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm maintains two variables to track the minimum cost for the 'up' and 'down' staircases. However, it implicitly creates two arrays (or similar data structures) of size N to store the minimum costs calculated at each step for both the increasing and decreasing sequences. These arrays enable the algorithm to make local decisions by referring to past computations. Therefore, the auxiliary space used scales linearly with the input size N, where N is the number of elements in the input array.

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 since an empty array is trivially both non-decreasing and non-increasing.
Array with one element	Return 0 since an array with a single element is trivially both non-decreasing and non-increasing.
Array with two elements: already non-decreasing	Return 0 as no changes are needed.
Array with two elements: already non-increasing	Return 0 as no changes are needed.
Array with two elements: needs one change	Return 1, as one change (either increasing or decreasing) makes it valid.
Array with all identical elements	Return 0, as an array with identical elements is both non-decreasing and non-increasing.
Array with maximum integer values (Integer.MAX_VALUE or Integer.MIN_VALUE)	Check for potential integer overflow issues when performing calculations to determine the number of operations needed.
Large array size that could lead to time limit exceeded	Optimize solution to use dynamic programming to avoid redundant calculations and keep the time complexity efficient (e.g., O(n)).

Empty or null input array

How to Handle:

Return 0 since an empty array is trivially both non-decreasing and non-increasing.

Array with one element

How to Handle:

Return 0 since an array with a single element is trivially both non-decreasing and non-increasing.

Array with two elements: already non-decreasing

How to Handle:

Return 0 as no changes are needed.

Array with two elements: already non-increasing

How to Handle:

Return 0 as no changes are needed.

Array with two elements: needs one change

How to Handle:

Return 1, as one change (either increasing or decreasing) makes it valid.

Array with all identical elements

How to Handle:

Return 0, as an array with identical elements is both non-decreasing and non-increasing.

Array with maximum integer values (Integer.MAX_VALUE or Integer.MIN_VALUE)

How to Handle:

Check for potential integer overflow issues when performing calculations to determine the number of operations needed.

Large array size that could lead to time limit exceeded

How to Handle:

Optimize solution to use dynamic programming to avoid redundant calculations and keep the time complexity efficient (e.g., O(n)).

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 are the possible ranges and data types of the numbers in the input array? Should I expect integers, floats, or a mix? Can the numbers be negative, zero, or only positive?
Is it always possible to make the array either non-decreasing or non-increasing with the operations allowed, or are there cases where it's impossible? If it's impossible, what should I return?
What is the size limit of the input array? I want to be mindful of memory constraints.
If there are multiple ways to make the array non-decreasing or non-increasing, does it matter which solution I choose, or should I optimize for the minimal number of changes?
Can you provide some examples of input arrays and their corresponding solutions to better understand the expected output?

Brute Force Solution

Approach

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

First, let's consider making the list non-decreasing. That means each number should be the same or bigger than the one before it.
Try changing the first number to every possible value. For each of these changes, see how many more changes we need to make to the rest of the numbers to make the whole list non-decreasing.
Then, go back and try changing the second number to every possible value, and again see how many changes that would take to make the list non-decreasing.
Repeat this for every number in the list. This process will identify how many changes are needed to make the array non-decreasing.
Next, do the same thing, but try to make the list non-increasing instead. That means each number should be the same or smaller than the one before it. Repeat the above process.
Finally, compare the number of changes it took to make the list non-decreasing versus the number of changes it took to make the list non-increasing. Choose the option that required the fewest changes.

Code Implementation

def make_array_non_decreasing_or_non_increasing(numbers):
    def calculate_changes_non_decreasing(array):
        number_of_changes = 0
        for index in range(1, len(array)):
            if array[index] < array[index - 1]:
                number_of_changes += array[index - 1] - array[index]
                array[index] = array[index - 1]
        return number_of_changes

    def calculate_changes_non_increasing(array):
        number_of_changes = 0
        for index in range(1, len(array)):
            if array[index] > array[index - 1]:
                number_of_changes += array[index] - array[index - 1]
                array[index] = array[index - 1]
        return number_of_changes

    minimum_changes = float('inf')

    # Iterate to explore every possible value for each number
    for index_to_change in range(len(numbers)):
        original_value = numbers[index_to_change]

        # We try every number in the array
        for new_value in numbers:

            # Create copies to avoid modifying the original array
            non_decreasing_attempt = numbers[:]
            non_increasing_attempt = numbers[:]
            non_decreasing_attempt[index_to_change] = new_value
            non_increasing_attempt[index_to_change] = new_value

            changes_non_decreasing = calculate_changes_non_decreasing(non_decreasing_attempt)
            changes_non_increasing = calculate_changes_non_increasing(non_increasing_attempt)

            # Count changes needed for current iteration.
            current_changes = min(changes_non_decreasing, changes_non_increasing) + 1
            if new_value != original_value:
                current_changes -= 1
            
            minimum_changes = min(minimum_changes, current_changes)

    non_decreasing_numbers = numbers[:]
    non_increasing_numbers = numbers[:]

    non_decreasing_changes_initial = calculate_changes_non_decreasing(non_decreasing_numbers)
    non_increasing_changes_initial = calculate_changes_non_increasing(non_increasing_numbers)

    minimum_changes = min(minimum_changes, non_decreasing_changes_initial, non_increasing_changes_initial)

    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 building two staircases, one going up and one going down.
For each number, decide what it would cost to make it fit on the 'up' staircase and what it would cost to make it fit on the 'down' staircase, considering the previous stair step.
Keep track of the minimum cost for the 'up' staircase and the 'down' staircase as you go along.
At the end, the minimum cost of either the 'up' staircase or the 'down' staircase is your answer.
Essentially, you're making the best local decision at each number, knowing the optimal cost to get to that number.

Code Implementation

def min_changes(sequence):
    sequence_length = len(sequence)
    if sequence_length <= 1:
        return 0

    increasing_changes = [0] * sequence_length
    decreasing_changes = [0] * sequence_length

    for i in range(1, sequence_length):
        increasing_changes[i] = float('inf')
        decreasing_changes[i] = float('inf')

        for j in range(i):
            # Calculate changes to make increasing
            if sequence[i] >= sequence[j]:
                increasing_changes[i] = min(increasing_changes[i], increasing_changes[j])
            else:
                increasing_changes[i] = min(increasing_changes[i], increasing_changes[j] + 1)

            # Calculate changes to make decreasing
            if sequence[i] <= sequence[j]:
                decreasing_changes[i] = min(decreasing_changes[i], decreasing_changes[j])
            else:
                decreasing_changes[i] = min(decreasing_changes[i], decreasing_changes[j] + 1)

    # Return the minimum of the two change counts
    return min(increasing_changes[sequence_length - 1], decreasing_changes[sequence_length - 1])

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 since an empty array is trivially both non-decreasing and non-increasing.
Array with one element	Return 0 since an array with a single element is trivially both non-decreasing and non-increasing.
Array with two elements: already non-decreasing	Return 0 as no changes are needed.
Array with two elements: already non-increasing	Return 0 as no changes are needed.
Array with two elements: needs one change	Return 1, as one change (either increasing or decreasing) makes it valid.
Array with all identical elements	Return 0, as an array with identical elements is both non-decreasing and non-increasing.
Array with maximum integer values (Integer.MAX_VALUE or Integer.MIN_VALUE)	Check for potential integer overflow issues when performing calculations to determine the number of operations needed.
Large array size that could lead to time limit exceeded	Optimize solution to use dynamic programming to avoid redundant calculations and keep the time complexity efficient (e.g., O(n)).

Empty or null input array

How to Handle:

Return 0 since an empty array is trivially both non-decreasing and non-increasing.

Array with one element

How to Handle:

Return 0 since an array with a single element is trivially both non-decreasing and non-increasing.

Array with two elements: already non-decreasing

How to Handle:

Return 0 as no changes are needed.

Array with two elements: already non-increasing

How to Handle:

Return 0 as no changes are needed.

Array with two elements: needs one change

How to Handle:

Return 1, as one change (either increasing or decreasing) makes it valid.

Array with all identical elements

How to Handle:

Return 0, as an array with identical elements is both non-decreasing and non-increasing.

Array with maximum integer values (Integer.MAX_VALUE or Integer.MIN_VALUE)

How to Handle:

Check for potential integer overflow issues when performing calculations to determine the number of operations needed.

Large array size that could lead to time limit exceeded

How to Handle:

Optimize solution to use dynamic programming to avoid redundant calculations and keep the time complexity efficient (e.g., O(n)).