Introduction

In this series of "Leetcode" posts I will publish solutions to leetcode problems. It is true that you can find most/lots of leetcode solutions on the web, but I will try to post my solutions to problems that are interesting or to problems for which the solutions out there are not well explained and deserve a better explanation.

The aim is to share knowledge, and that people who are studying, preparing for interviews, or just practicing, can become better at solving problems. Please feel free to comment if you have a suggestion or a different approach!

Problem statement

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most 1 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).

Summary: You have a method that returns true is the array, passed as input, can become increasing (non-decreasing), meaning the values in the array are equal or greater that the previous element in the array. You can change at most one element in the array to make this happen.

Solution

The solutions provided by leetcode are quite confusing (and the code only in python). And the optimal solution seems more complicated than it is.

First Solution

The main idea

Go through the array, if there is an element that violates the constraint (increasing), then change/mark it. Keep going through the array, if another violations occurs, then return false as we cannot change more than once. If there hasn't been any violation or we changed at most once then return true.

Explanation and Code

An increasing array should be something like this:

[1,2,2,3,4,5,5]

Every element in the array: array[i], is less than or equal than the next element: array[i+1].

array[i] <= array[i+1]

So the input array, could potentially violate this constraint at some point:

[...2,8,5,...]

In the example above, which represents an array, at some point, one of the elements is not greater or equal than the next. In this case:

8 is not greater than or equal to 2

So just do as the problem says, change it in order to fix it!

We need to change some element so that the constraints are not violated. Now the question is, what to change, which value?

The key thing here is to remember that we always need to modify the array to a state that is according to the constraints, in this case we must make the elements of the array increasing.

So we have the following constraints about the state of the array at any index:

1. Any element before index "i": array[i-1], should be less than or equal to the element at index "i": array[i]

2. Any element after index "i": array[i+1], should be greater than or equal to the element at index "i": array[i]

We need these 2 constraints to guarantee that the array values are increasing and we need to maintain them.

Whatever is the change we choose to make, those 2 constraints must be maintained after the change.

At this point, the solution is easy if we consider the "combinations" we could have with both previous and next elements in the array, in reference to the index where the constraints are not maintained.

1. If the previous element in the array is greater than the next element, then we need to change the next element to the value of the current element:

array[i+1] = array[i]

Example:

[...8,10,5,...] // Not in increasing order, 10 > 5

array[i] = 10
array[i-1] > array[i+1]
8 > 5

So to fix we change array[i+1] to array[i]:

[...8,10,10,...]

This is the only way we will guarantee that we maintain the increasing order and comply with the constraints.

1. If the previous element in the array is less than the next element, we need to change the current element to the value of the next element:

array[i] = array[i+1]

[...4,9,7...] // Not in increasing order, 9 > 7

array[i] = 9
array[i-1] < array[i+1]
4 > 7

So to fix it we change array[i] to array[i+1]:

[...4,7,7,...]

This is the only way we will guarantee that we maintain the increasing order and comply with the constraints.

Note that we could also change array[i+1] to 9, but that could mess up the next elements after array[i+1].

The code is the following:

    public boolean checkPossibility(int[] nums) {
        boolean changed = false;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (changed) return false;
                if (i != 0 && nums[i - 1] > nums[i + 1]) {
                    nums[i + 1] = nums[i];
                }
                changed = true;
            }
        }
        return true;
    }

In the actual code we don't really need to change for the second case, where array[i-1] < array[i+1], because we are gonna keep checking the array with array[i+i], and because that value is not changed at all, we can ignore the "actual" change which occurs at array[i].

What we always need, is to have a boolean variable, that indicates if we previously did a change on the array. So in the case we did and the variable "changed" is true, then we can no longer do any other change and we should return false if another change is required.

The code is simple and clear. One disadvantage of this approach is that we are mutating the input, which is not good if we try to think in terms of pure functions.

Complexity

• Time: O(n), we only loop once through the whole array
• Space: O(1), we are only creating a new variable: "changed", however this does not depend on the size of the input, hence, we have constant space complexity.

Second solution

If you really don't want to modify the input, there are ways to avoid this. One of which is the following:

   public boolean checkPossibility2(int[] nums) {
        boolean changed = false;
        int currentValue = nums[0];
        for (int i = 0; i < nums.length - 1; i++) {
            if (currentValue > nums[i + 1]) {
                if (changed) return false;
                if (i != 0 && nums[i - 1] > nums[i + 1]) {
                    currentValue = nums[i];
                } else {
                    currentValue = nums[i + 1];
                }
                changed = true;
            } else {
                currentValue = nums[i + 1];
            }
        }
        return true;
    }

The idea is the same, but we need to have another variable: "currentValue" to hold the currentValue in case it changes.

Another solution:

You could also do the same as approach 1 and change the original array, but save the changed value and index, so at the end of the for loop you replace back the original value. While this solution does not seem to change the original input, it could lead to problems if you have concurrent access to the method, as the input can be different at some point in time. Obviously this is not an issue for this problem, but it is something to consider when working in concurrent applications, and always good to remember.