> For the complete documentation index, see [llms.txt](https://twchen.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://twchen.gitbook.io/leetcode/array/non-decreasing-array.md).

# 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;
    }
};
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://twchen.gitbook.io/leetcode/array/non-decreasing-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.