# LeetCode 665: Non-decreasing Array

## Problem Restatement

We are given an integer array `nums`.

We need to check whether it can become non-decreasing by modifying at most one element. A non-decreasing array means every element is less than or equal to the next element. The official statement defines this condition as `nums[i] <= nums[i + 1]` for every valid index `i`.

Return `True` if this is possible.

Otherwise, return `False`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | `True` if the array can become non-decreasing |
| Allowed change | Modify at most one element |
| Required order | `nums[i] <= nums[i + 1]` for every adjacent pair |

Example function shape:

```python
def checkPossibility(nums: list[int]) -> bool:
    ...
```

## Examples

Consider:

```python
nums = [4, 2, 3]
```

This can become non-decreasing by changing `4` to a smaller value:

```python
[1, 2, 3]
```

So the answer is:

```python
True
```

Now consider:

```python
nums = [4, 2, 1]
```

There are two drops:

```text
4 > 2
2 > 1
```

One modification cannot fix both problems.

So the answer is:

```python
False
```

Another important example:

```python
nums = [3, 4, 2, 3]
```

There is a violation:

```text
4 > 2
```

If we lower `4` to `2`, the array becomes:

```python
[3, 2, 2, 3]
```

This creates a new violation:

```text
3 > 2
```

If we raise `2` to `4`, the array becomes:

```python
[3, 4, 4, 3]
```

This still has:

```text
4 > 3
```

So the answer is:

```python
False
```

## First Thought: Count Violations

The array is invalid wherever:

```python
nums[i] > nums[i + 1]
```

If this happens more than once, we should return `False`.

But counting violations alone is not enough.

For example:

```python
[3, 4, 2, 3]
```

has only one visible violation:

```text
4 > 2
```

but it still cannot be fixed with one modification.

So when we see a violation, we must decide whether it can be repaired safely.

## Key Insight

Suppose we find:

```python
nums[i] > nums[i + 1]
```

There are two possible ways to fix this local problem.

We can lower the left value:

```python
nums[i] = nums[i + 1]
```

or raise the right value:

```python
nums[i + 1] = nums[i]
```

The safer choice depends on the previous element.

If `i == 0`, there is no previous element, so lowering `nums[i]` is safe.

Otherwise, if:

```python
nums[i - 1] <= nums[i + 1]
```

then lowering `nums[i]` is safe, because it keeps the relation with the previous element valid.

If that condition is false, lowering `nums[i]` would create:

```python
nums[i - 1] > nums[i]
```

So we must raise `nums[i + 1]` instead.

## Algorithm

Scan the array from left to right.

Keep a counter called `changes`.

For each index `i` from `0` to `n - 2`:

1. If `nums[i] <= nums[i + 1]`, continue.
2. Otherwise, we found a violation.
3. Increase `changes`.
4. If `changes > 1`, return `False`.
5. If `i == 0` or `nums[i - 1] <= nums[i + 1]`, lower `nums[i]`.
6. Otherwise, raise `nums[i + 1]`.

If the scan finishes, return `True`.

## Correctness

The algorithm scans every adjacent pair.

Whenever it finds a violation `nums[i] > nums[i + 1]`, at least one of those two elements must be modified. No other element can directly fix this adjacent inversion.

If this happens more than once, then at least two modifications are needed, so returning `False` is correct.

For the first violation, the algorithm chooses a modification that preserves the already-scanned prefix.

If lowering `nums[i]` is safe, it does so. This is safe when `i == 0` or when `nums[i - 1] <= nums[i + 1]`.

If lowering `nums[i]` is not safe, then raising `nums[i + 1]` is the only possible local repair that does not break the prefix before `i`.

After this repair, the scan continues. Since the algorithm allows only one repair and immediately rejects a second violation, it returns `True` exactly when the array can be made non-decreasing with at most one modification.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` | Only a counter is used |

## Implementation

```python
from typing import List

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        changes = 0

        for i in range(len(nums) - 1):
            if nums[i] <= nums[i + 1]:
                continue

            changes += 1

            if changes > 1:
                return False

            if i == 0 or nums[i - 1] <= nums[i + 1]:
                nums[i] = nums[i + 1]
            else:
                nums[i + 1] = nums[i]

        return True
```

## Code Explanation

We count how many fixes are needed:

```python
changes = 0
```

Then we scan adjacent pairs:

```python
for i in range(len(nums) - 1):
```

If the pair is already valid, we do nothing:

```python
if nums[i] <= nums[i + 1]:
    continue
```

If the pair is invalid, we need one modification:

```python
changes += 1
```

More than one modification is not allowed:

```python
if changes > 1:
    return False
```

Now we choose how to repair the current violation.

If we are at the beginning, or if the previous element can still fit before `nums[i + 1]`, we lower `nums[i]`:

```python
if i == 0 or nums[i - 1] <= nums[i + 1]:
    nums[i] = nums[i + 1]
```

Otherwise, lowering `nums[i]` would break the previous pair, so we raise `nums[i + 1]`:

```python
else:
    nums[i + 1] = nums[i]
```

If the scan finishes, the array can be fixed with at most one change:

```python
return True
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.checkPossibility([4, 2, 3]) is True
    assert s.checkPossibility([4, 2, 1]) is False
    assert s.checkPossibility([3, 4, 2, 3]) is False
    assert s.checkPossibility([1, 2, 3]) is True
    assert s.checkPossibility([1]) is True
    assert s.checkPossibility([2, 3, 3, 2, 4]) is True
    assert s.checkPossibility([1, 4, 1, 2]) is True
    assert s.checkPossibility([5, 7, 1, 8]) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[4,2,3]` | Can be fixed by lowering the first value |
| `[4,2,1]` | Needs more than one modification |
| `[3,4,2,3]` | One violation but impossible to repair globally |
| `[1,2,3]` | Already non-decreasing |
| `[1]` | Single element is always valid |
| `[2,3,3,2,4]` | Can be fixed by raising one value |
| `[1,4,1,2]` | Can be fixed by lowering the middle value |
| `[5,7,1,8]` | Checks decision using the previous element |