Jobs

Interviews

Discussions

Non-decreasing Array

Medium

Asked by:

31 views

Topics:

Arrays

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Example 1:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: nums = [4,2,1]
Output: false
Explanation: You cannot get a non-decreasing array by modifying at most one element.

Constraints:

n == nums.length
1 <= n <= 10⁴
-10⁵ <= nums[i] <= 10⁵

Try coding it in LeetCode

Non-decreasing Array

Medium

Asked by:

31 views

Topics:

Arrays

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Example 1:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: nums = [4,2,1]
Output: false
Explanation: You cannot get a non-decreasing array by modifying at most one element.

Constraints:

n == nums.length
1 <= n <= 10⁴
-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 value ranges and data types for the integers within the input array?
Can the input array be empty or null? If so, what should I return?
If there are multiple possible modifications that result in a non-decreasing array, am I allowed to return true as soon as I find one, or am I expected to find a "best" solution in some sense?
Are there any memory constraints that I should be aware of?
Is it acceptable to modify the input array directly, or should I create a copy to work with?

Brute Force Solution

Approach

The brute force approach for this problem involves checking every possible way to modify the given list of numbers. We'll try changing each number, one at a time, to see if it makes the list non-decreasing. It's like trying every single possible adjustment.

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

First, look at the list as it is. Check if the numbers are already in non-decreasing order (each number is greater than or equal to the one before it). If they are, you're done.
If the list isn't non-decreasing, start by going through each number in the list, one at a time.
For each number, try changing it to every other possible value. A good range of values to try is the values of the number before it, and the number after it.
After changing a number, check if the entire list is now in non-decreasing order.
If changing one number makes the list non-decreasing, you've found a solution.
If you try changing every number to every possible value, and none of those changes make the list non-decreasing, then it's impossible to make the list non-decreasing by changing only one number.

Code Implementation

def non_decreasing_array_brute_force(numbers):
    # Check if the original array is already non-decreasing
    if is_non_decreasing(numbers):
        return True

    list_length = len(numbers)
    for index_to_change in range(list_length):
        original_value = numbers[index_to_change]

        # Try changing the number to the value before it
        if index_to_change > 0:
            numbers[index_to_change] = numbers[index_to_change - 1]
            if is_non_decreasing(numbers):
                return True

        # Try changing the number to the value after it
        if index_to_change < list_length - 1:
            numbers[index_to_change] = numbers[index_to_change + 1]
            if is_non_decreasing(numbers):
                return True

        # Restore the original value before trying the next index
        numbers[index_to_change] = original_value

    return False

def is_non_decreasing(numbers):
    for index in range(len(numbers) - 1):
        # If a number is smaller than the previous, it's not non-decreasing
        if numbers[index] > numbers[index + 1]:
            return False

    return True

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements of the array. For each element, it explores modifying it to potentially other values, and then checks if the entire modified array is non-decreasing. The non-decreasing check requires iterating through the array, taking O(n) time. Since we perform this O(n) check for each of the n elements during the modification attempts, the overall time complexity is O(n * n), which simplifies to O(n²).

Space Complexity

O(N) – The brute force approach involves checking every possible modification of the input array, which entails creating a copy of the input array of size N for each modification being checked. Although the algorithm doesn't explicitly create and maintain a separate large data structure, implicitly, to test each modification, a copy of the array may be created or the original array may be modified and then restored. In the worst case, each number may be changed resulting in the creation of multiple copies or modifications of the original array. Therefore the auxiliary space is O(N) due to the need to potentially store a copy of the modified array.

Optimal Solution

Approach

The goal is to see if we can make a list of numbers be in non-decreasing order by changing at most one number. We'll walk through the list and if we find a problem, we'll try to fix it by changing one of the numbers involved in the problem.

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

Go through the list of numbers from the beginning to the end.
Watch out for any place where a number is bigger than the number that comes after it. This is where the list is not in non-decreasing order.
If you find such a place, try fixing it. You have two options: either change the bigger number to be smaller, or change the smaller number to be bigger. Choose the option that keeps the list as close to its original order as possible.
Check if the list is now in non-decreasing order. If you didn't find any problem spots to begin with, or if you were able to fix the one problem spot you found, then the list can be made non-decreasing.
If you find more than one problem spot, or if you can't fix the problem spot in a way that keeps the list non-decreasing, then the list cannot be made non-decreasing by changing just one number.

Code Implementation

def can_be_non_decreasing(number_list):
    number_of_errors = 0

    for index in range(len(number_list) - 1):
        if number_list[index] > number_list[index + 1]:
            # Found a non-decreasing violation
            number_of_errors += 1

            if number_of_errors > 1:
                return False

            # Attempt to correct the violation
            if index > 0 and number_list[index - 1] > number_list[index + 1]:
                # Modifying the next element could violate previous order
                number_list[index + 1] = number_list[index]
            else:
                # Modify current element to fix the order.
                number_list[index] = number_list[index + 1]

    return True

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through the input array nums once, checking for non-decreasing order at each step. When a violation of the non-decreasing order is found, it attempts to correct it with a local modification. This single pass through the array determines if at most one modification can result in a non-decreasing array. Therefore, the time complexity is directly proportional to the number of elements in the array, represented by n.

Space Complexity

O(1) – The algorithm iterates through the input array, but it doesn't create any auxiliary data structures like lists, maps, or sets to store intermediate results. It only uses a few variables to keep track of the current index and potentially a flag to indicate whether a modification has been made. Therefore, the space required remains constant regardless of the size of the input array, N.

Edge Cases

Case	How to Handle
Empty array	Return true because an empty array is considered non-decreasing.
Array with one element	Return true because an array with one element is considered non-decreasing.
Array with two elements in non-decreasing order	Return true because it is already non-decreasing.
Array with two elements in decreasing order	Return true because we can modify one element to make it non-decreasing.
Array with all elements equal	Return true because the array is already non-decreasing.
Array with negative numbers and zeros	The comparison nums[i] <= nums[i + 1] works correctly with negative numbers and zeros.
Array where the first violation is near the beginning and requires modifying the earlier element	The algorithm needs to consider modifying either the i-th or (i+1)-th element, and choose the one that yields a non-decreasing array.
Array where the first violation is near the end and requires modifying the later element	The algorithm needs to correctly handle the boundary conditions when the violation occurs near the end of the array.

Empty array

How to Handle:

Return true because an empty array is considered non-decreasing.

Array with one element

How to Handle:

Return true because an array with one element is considered non-decreasing.

Array with two elements in non-decreasing order

How to Handle:

Return true because it is already non-decreasing.

Array with two elements in decreasing order

How to Handle:

Return true because we can modify one element to make it non-decreasing.

Array with all elements equal

How to Handle:

Return true because the array is already non-decreasing.

Array with negative numbers and zeros

How to Handle:

The comparison nums[i] <= nums[i + 1] works correctly with negative numbers and zeros.

Array where the first violation is near the beginning and requires modifying the earlier element

How to Handle:

The algorithm needs to consider modifying either the i-th or (i+1)-th element, and choose the one that yields a non-decreasing array.

Array where the first violation is near the end and requires modifying the later element

How to Handle:

The algorithm needs to correctly handle the boundary conditions when the violation occurs near the end of the array.

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 value ranges and data types for the integers within the input array?
Can the input array be empty or null? If so, what should I return?
If there are multiple possible modifications that result in a non-decreasing array, am I allowed to return true as soon as I find one, or am I expected to find a "best" solution in some sense?
Are there any memory constraints that I should be aware of?
Is it acceptable to modify the input array directly, or should I create a copy to work with?

Brute Force Solution

Approach

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

First, look at the list as it is. Check if the numbers are already in non-decreasing order (each number is greater than or equal to the one before it). If they are, you're done.
If the list isn't non-decreasing, start by going through each number in the list, one at a time.
For each number, try changing it to every other possible value. A good range of values to try is the values of the number before it, and the number after it.
After changing a number, check if the entire list is now in non-decreasing order.
If changing one number makes the list non-decreasing, you've found a solution.
If you try changing every number to every possible value, and none of those changes make the list non-decreasing, then it's impossible to make the list non-decreasing by changing only one number.

Code Implementation

def non_decreasing_array_brute_force(numbers):
    # Check if the original array is already non-decreasing
    if is_non_decreasing(numbers):
        return True

    list_length = len(numbers)
    for index_to_change in range(list_length):
        original_value = numbers[index_to_change]

        # Try changing the number to the value before it
        if index_to_change > 0:
            numbers[index_to_change] = numbers[index_to_change - 1]
            if is_non_decreasing(numbers):
                return True

        # Try changing the number to the value after it
        if index_to_change < list_length - 1:
            numbers[index_to_change] = numbers[index_to_change + 1]
            if is_non_decreasing(numbers):
                return True

        # Restore the original value before trying the next index
        numbers[index_to_change] = original_value

    return False

def is_non_decreasing(numbers):
    for index in range(len(numbers) - 1):
        # If a number is smaller than the previous, it's not non-decreasing
        if numbers[index] > numbers[index + 1]:
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Go through the list of numbers from the beginning to the end.
Watch out for any place where a number is bigger than the number that comes after it. This is where the list is not in non-decreasing order.
If you find such a place, try fixing it. You have two options: either change the bigger number to be smaller, or change the smaller number to be bigger. Choose the option that keeps the list as close to its original order as possible.
Check if the list is now in non-decreasing order. If you didn't find any problem spots to begin with, or if you were able to fix the one problem spot you found, then the list can be made non-decreasing.
If you find more than one problem spot, or if you can't fix the problem spot in a way that keeps the list non-decreasing, then the list cannot be made non-decreasing by changing just one number.

Code Implementation

def can_be_non_decreasing(number_list):
    number_of_errors = 0

    for index in range(len(number_list) - 1):
        if number_list[index] > number_list[index + 1]:
            # Found a non-decreasing violation
            number_of_errors += 1

            if number_of_errors > 1:
                return False

            # Attempt to correct the violation
            if index > 0 and number_list[index - 1] > number_list[index + 1]:
                # Modifying the next element could violate previous order
                number_list[index + 1] = number_list[index]
            else:
                # Modify current element to fix the order.
                number_list[index] = number_list[index + 1]

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array	Return true because an empty array is considered non-decreasing.
Array with one element	Return true because an array with one element is considered non-decreasing.
Array with two elements in non-decreasing order	Return true because it is already non-decreasing.
Array with two elements in decreasing order	Return true because we can modify one element to make it non-decreasing.
Array with all elements equal	Return true because the array is already non-decreasing.
Array with negative numbers and zeros	The comparison nums[i] <= nums[i + 1] works correctly with negative numbers and zeros.
Array where the first violation is near the beginning and requires modifying the earlier element	The algorithm needs to consider modifying either the i-th or (i+1)-th element, and choose the one that yields a non-decreasing array.
Array where the first violation is near the end and requires modifying the later element	The algorithm needs to correctly handle the boundary conditions when the violation occurs near the end of the array.

Empty array

How to Handle:

Return true because an empty array is considered non-decreasing.

Array with one element

How to Handle:

Return true because an array with one element is considered non-decreasing.

Array with two elements in non-decreasing order

How to Handle:

Return true because it is already non-decreasing.

Array with two elements in decreasing order

How to Handle:

Return true because we can modify one element to make it non-decreasing.

Array with all elements equal

How to Handle:

Return true because the array is already non-decreasing.

Array with negative numbers and zeros

How to Handle:

The comparison nums[i] <= nums[i + 1] works correctly with negative numbers and zeros.

Array where the first violation is near the beginning and requires modifying the earlier element

How to Handle:

The algorithm needs to consider modifying either the i-th or (i+1)-th element, and choose the one that yields a non-decreasing array.

Array where the first violation is near the end and requires modifying the later element

How to Handle:

The algorithm needs to correctly handle the boundary conditions when the violation occurs near the end of the array.