# Non-decreasing Array

## Description

Given an array 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 `array[i] <= array[i + 1]` holds for every `i` (1 <= i < n).

**Example 1:**

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

**Example 2:**

```
Input: [4,2,1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.
```

**Note:** The `n` belongs to \[1, 10,000].

## Solutions

### My solution

Idea: `nums[0..i]` and `nums[j..n-1]` are longest non-decreasing sequences starting at `nums[0]` and ending at `nums[n-1]`, respectively.

```cpp
class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int i = 0, n = nums.size();
        while(i + 1 < n && nums[i] <= nums[i + 1]) ++i;

        // i == n - 1, the whole array is non-decreasing
        // i == n - 2, we can change the last element to make the array non-decreasing.
        if(i >= n - 2) return true;
        int j = n - 1;

        // no need to check j > 0 because
        // nums[i] > nums[i + 1]
        // so the while loop must terminate
        while(nums[j - 1] <= nums[j]) --j;
        
        // if j - i > 1, at least two reverse pairs
        // i.e., (nums[i], nums[i + 1]) and (nums[j - 1], nums[j])
        if(j - i > 1) return false;

        // i + 1 == j
        // only one reverse pair
        // check if it's possible to change either nums[i] or nums[j]
        // to make the array non-decreasing
        return i == 0 || nums[i - 1] <= nums[j] || nums[i] <= nums[j + 1];
    }
};
```

### Solution 1

Explanation: if there is a reverse pair (`nums[i]`, `nums[i + 1]`). We need to change either `nums[i]` or `nums[i + 1]`. If `i > 0 && nums[i - 1] > nums[i + 1]`, we must change `nums[i + 1]`. Otherwise, we can change either `nums[i]` or `nums[i + 1]`. But we prefer changing `nums[i]` because if we can change `nums[i + 1]` (i.e., let `nums[i + 1] = nums[i]`) to make the array non-decreasing, then we can also change `nums[i]` (i.e., let `nums[i] = nums[i + 1]`) to make the array non-decreasing (the other direction is not true).

```cpp
class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int count = 0;
        // we can use some variable to remember the modified element
        // if we don't want the array to be changed when the function returns.
        //int idx = -1, val = -1;
        for(int i = 0; i + 1 < nums.size(); ++i){
            if(nums[i] > nums[i + 1]){
                if(++count > 1)
                    return false;
                // if i == 0 || nums[i - 1] <= nums[i + 1], we can change nums[i] to nums[i + 1]
                // otherwise, we have to change nums[i + 1] to nums[i]
                if(i > 0 && nums[i - 1] > nums[i + 1]){
                    //idx = i + 1;
                    //val = nums[i + 1];
                    nums[i + 1] = nums[i];
                }
            }
        }
        //if(idx != -1) nums[idx] = val;
        return true;
    }
};
```

### Solution 2

Credit: <https://leetcode.com/problems/non-decreasing-array/discuss/106842/The-easiest-python-solution....>

```cpp
class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int count = 0;
        int n = nums.size();
        for(int i = 0; i + 1 < n; ++i){
            if(nums[i] > nums[i + 1]){
                ++count;
                if(count > 1 || i > 0 && i + 2 < n && nums[i - 1] > nums[i + 1] && nums[i] > nums[i + 2])
                    return false;
            }
        }
        return true;
    }
};
```