# [Java/C++] Simple greedy like solution with explanation

• This problem is like a greedy problem. When you find `nums[i-1] > nums[i]` for some `i`, you will prefer to change `nums[i-1]`'s value, since a larger `nums[i]` will give you more risks that you get inversion errors after position `i`. But, if you also find `nums[i-2] > nums[i]`, then you have to change `nums[i]`'s value instead, or else you need to change both of `nums[i-2]`'s and `nums[i-1]`'s values.

Java version:

`````` public boolean checkPossibility(int[] nums) {
int cnt = 0;                                                                    //the number of changes
for(int i = 1; i < nums.length && cnt<=1 ; i++){
if(nums[i-1] > nums[i]){
cnt++;
if(i-2<0 || nums[i-2] <= nums[i])nums[i-1] = nums[i];                    //modify nums[i-1] of a priority
else nums[i] = nums[i-1];                                                //have to modify nums[i]
}
}
return cnt<=1;
}
``````

C++ version:

``````bool checkPossibility(vector<int>& nums) {
int cnt = 0;                                                                    //the number of changes
for(int i = 1; i < nums.size() && cnt<=1 ; i++){
if(nums[i-1] > nums[i]){
cnt++;
if(i-2<0 || nums[i-2] <= nums[i])nums[i-1] = nums[i];                    //modify nums[i-1] of a priority
else nums[i] = nums[i-1];                                                //have to modify nums[i]
}
}
return cnt<=1;
}
``````

• Nice explanation！

• Nice Explanation. One optimization though, we can terminate the loop as soon as cnt > 1

`if (cnt > 1) return false;`

• @abhijeet15 he included that in the for-loop as "cnt <= 1" already.

• Same idea. If number of breaks for a non-decreasing order is more than 1, we are bound to change more than 1 element. So, we stop and return false.

If break happens at `boundaries`, we can surely change that 1 element, so it will always be `true`.

If we find exact 1 break of sequences, we check with `break_index-1` and `break_index+1` element and if they happen to be `non-decreasing`, then we can make exactly one change of `nums[break_index]` to make the sequence non-decreasing.

If we cannot, similarly we check with `break_index-2` and `break_index`, and if they are non-decreasing, we can change `nums[break_index-1]` to make it non-decreasing.

If nothing is possible, we just check with `cnt` value and return accordingly.

``````public class Solution {
public boolean checkPossibility(int[] nums) {

int cnt = 0;
int len = nums.length;
int break_index = -1;

for(int i=0;i<len-1 && cnt < 2;++i){
if(nums[i] > nums[i+1]){
cnt += 1;
break_index = i+1;
}
}

if(cnt > 1) return false;
if(break_index == len-1 || break_index == 1) return true;
if(cnt == 1 && nums[break_index-1] <= nums[break_index+1]) return true;
if(cnt == 1 && nums[break_index-2] <= nums[break_index]) return true;

return cnt == 0;
}
}
``````

• @vivek_23 Thank you for your answer. I found it easier to understand than the other ones.

I had one question though - why do you think that we need to check both (`break_index-1` and `break_index+1`) and (`break_index-2` and `break_index`)? Won't the second case (`break_index-2` and `break_index`) be accounted for, at previous `i` (due to the (`break_index-1` and `break_index+1`) checks)?

To be precise, why do we have to check elements at `i-1` and `i+1` as well as at `i-2` and `i`? Wouldn't those at `i-2` and `i` be checked in the previous iteration (`i-1`)?

• @BatCoder

Those 2 checks are required because we need to decide which index to change, to `join` the 2 non decreasing sequences and if neither of them fits, we return false.

For example, let's take [2,3,3,3,3,2,4]
Now, the break_index here is `5`. So, the 2 sequences are [2,3,3,3,3] and [2,4].
To join them, the check `nums[break_index-1] <= nums[break_index+1]`, satisfies the non decreasing property and we can change `nums[break_index]` to `3` for joining.

Let's take another example - [1,3,5,3,4]
break_index is `3`. Here, `nums[break_index-2] <= nums[break_index]` fits correctly whereas the other case doesn't which would have forced us to make 2 changes. But, here its quite possible to make a single change, i.e., to make `nums[break_index-1]` to `3` for joining.

Last case which fits neither of the 2 checks- [3,4,2,3], so we return false.

I hope its clear to you now.

• Sharing my easy O(N) solution, without modifying the input. click here for more explanation.

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

• @vivek_23
Perfectly clear. Thank you, Vivek!

• Hi, what if the there could exist more than 2 modification, for example 3, 4 or some predefined value k? Any idea?

• Got the same idea.
Python version:

``````class Solution(object):
def checkPossibility(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if len(nums) <= 1:
return True
violation_count = 0
for i in range(1, len(nums)):
if nums[i] < nums[i - 1]:
violation_count += 1
if violation_count == 2:
return False
if i - 2 >= 0 and nums[i - 2] > nums[i]: # have to promote nums[i]
nums[i] = nums[i - 1]
return True``````

• Sweet... how can I prove the correctness?

• Nice! Thank you!

• Here is my Python solution

``````class Solution(object):
def checkPossibility(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
cnt = 0
for i in range(1, len(nums)):
if cnt > 1: return False
# use 1,2,3 to denote i-2 i-1 i, 1 largest
if nums[i-1] > nums[i]:
cnt += 1
if i < 2 or nums[i-2] <= nums[i]:
# from 3 1 2 to 3 2 2
nums[i-1] = nums[i]
else:
# from 2 1 3 to 2 1 1
nums[i] = nums[i-1]

return cnt <= 1
``````

• if we delete the condition i-2<0 the code will also been accepted.

• @liyiye I guess you are using C++. When you remove `i - 2 <0`, you will use `nums[-1]` if `i=1`. In C++, it's called undifined behavior. `std::vector` operator `[]` won't throw any out of range error, and you might get `nums[-1] = 0` actually. If you use `std::vector::at` instead, it will throw `std::out_of_range`.

You can have a test of `nums = {2, -2, -1}`, there would be different results while removing or not removing `i - 2 <0`.

• ``````class Solution {
public boolean checkPossibility(int[] nums) {
boolean modified = false;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < nums[i - 1]) {
if (modified) {
return false;
} else {
modified = true;
if (i - 2 >= 0 && nums[i] < nums[i - 2]) {
nums[i] = nums[i - 1];
}
}
}
}
return true;
}
}
``````

• Great solution. Below is a little explanation for those having trouble understanding.

The problem requires that every number has to be equal or greater than previous number.
If we encounter a failing condition where the number is not greater or equal to previous (smaller than previous) we need to make a correction. Correction can be made in either of two ways:

1. Make the previous number smaller or equal to current number
2. Make the current number equal to previous number

We can do (1) as long as the number at position i-2 is equal or lower than the current element. (if i-2 is valid)
In case 1 below we can do this at (3) (i = 2) as the element 1 (i = 0) fulfills 1 <= 3. We can replace 7 with 3.
However, this cannot be done in case 2 as 4 <= 3 does not satisfy.

Correction with technique (1) takes priority as there is no risk in lowering the value but there is a risk associated if the value is increased. (Consider scenario in case 1 if we replace 3 with 7, it will fail to satisfy the condition for the last element)

We have to make correction with (2) if we cannot achieve it by (1). In which case we increase the value of current element by matching previous element. In case 2, we replace 3 with 7.

Also we only compare condition with the previous element only because as we move forward we know the previous numbers are already validated .

``````Case 1:
7
/\    4
/  \  /
/    \/
/      3
1

Case 2:
9
/
7    /
/\  /
/  \/
/    3
4
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.