# Non-decreasing Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/non-decreasing-array)
Canonical: https://scaleengineer.com/dsa/problems/non-decreasing-array
**Data structures:** Array
**Companies:** [Cashfree](https://scaleengineer.com/companies/cashfree)
---
## Problem
Given an array `nums` with `n` integers, your task is to check if it could become non-decreasing by modifying **at most one 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`).

**Example 1:**

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

**Example 2:**

**Input:** nums = [4,2,1]
**Output:** false
**Explanation:** You cannot get a non-decreasing array by modifying at most one element.

**Constraints:**

* `n == nums.length`
* `1 <= n <= 104`
* `-105 <= nums[i] <= 105`

# Approaches
## Brute Force Simulation
This approach simulates the process of modifying each element one by one and checking if the resulting array becomes non-decreasing. If we find any such modification that works, we can conclude it's possible. The simulation is done by effectively removing each element in turn and checking if the remaining elements form a non-decreasing sequence. If they do, it implies the original element could have been changed to a suitable value.
**Time:** O(N^2), where N is the number of elements in the array. The main loop runs N times, and the helper function `isSorted` also runs in O(N) time, leading to a total complexity of O(N*N). · **Space:** O(1) if the check is done in-place without creating a new array, as shown in the provided snippet. If a new array is created in each iteration, the space complexity would be O(N).
**Pros:** Simple to understand and implement.; Directly simulates the condition of fixing the array by altering one element.
**Cons:** Inefficient for large arrays due to its quadratic time complexity.; Creates a new array in every iteration, which can be memory-intensive for large inputs.
### Explanation
The brute-force strategy systematically checks every possibility. Since we can modify at most one element, we can iterate through each element of the array and consider it as the one to be modified. For each element `nums[i]`, we test if changing its value can make the entire array non-decreasing.

A simple way to perform this test is to temporarily remove `nums[i]` from the array and check if the remaining `n-1` elements are non-decreasing. If they are, it means a 'slot' exists between `nums[i-1]` and `nums[i+1]` where `nums[i]` could be placed, thus making the whole array non-decreasing. For example, if we have `[..., 5, 10, 6, ...]` and we remove `10`, the remaining sequence `[..., 5, 6, ...]` is locally ordered. This implies we could have changed `10` to a value like `5` or `6` to fix the array.

The algorithm iterates through each index `i`, creates a temporary array without `nums[i]`, and checks if this temporary array is sorted. If this condition is met for any `i`, we return `true`. If the loop finishes without success, it means no single modification can solve the problem, so we return `false`. This also correctly handles arrays that are already sorted, as removing any element from a sorted array leaves a sorted array.

```java
class Solution {
    public boolean checkPossibility(int[] nums) {
        // Check the case where the array is already sorted (0 modifications)
        if (isSorted(nums, -1)) {
            return true;
        }

        // Try modifying at each position
        for (int i = 0; i < nums.length; i++) {
            // Check if the array becomes sorted if we ignore the element at index i
            if (isSorted(nums, i)) {
                return true;
            }
        }

        return false;
    }

    // Helper function to check if an array is sorted, ignoring one index
    private boolean isSorted(int[] nums, int skipIndex) {
        int prev = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (i == skipIndex) {
                continue;
            }
            if (nums[i] < prev) {
                return false;
            }
            prev = nums[i];
        }
        return true;
    }
}
```
### Algorithm
1. Define a helper function `isSorted(arr)` that checks if an array is non-decreasing in O(N) time.
2. Check if the input array `nums` is already sorted using the helper function. If it is, return `true` as zero modifications are needed.
3. Iterate through the array with an index `i` from `0` to `n-1`.
4. In each iteration, simulate the modification of the element `nums[i]`. A robust way to simulate this is to create a new temporary array `temp` that contains all elements of `nums` except for `nums[i]`.
5. Check if this `temp` array is sorted using the `isSorted` helper function.
6. If `temp` is sorted, it means that the original array could be made non-decreasing by appropriately changing the value of `nums[i]`. Therefore, return `true`.
7. If the loop completes without finding any such `i`, it means that modifying any single element is not sufficient. Return `false`.

## Single Pass Greedy Approach
This approach iterates through the array just once to find any violation of the non-decreasing property. A violation occurs when `nums[i] > nums[i+1]`. If more than one such violation is found, it's impossible to fix with one modification. If exactly one violation is found, we need to check if it can be resolved by changing either `nums[i]` or `nums[i+1]` without causing a new violation.
**Time:** O(N), where N is the number of elements. We iterate through the array only once. · **Space:** O(1), as we only use a few variables to keep track of the state. The input array is modified in-place in this implementation, but this does not affect the asymptotic space complexity.
**Pros:** Highly efficient with linear time complexity.; Space-efficient as it operates with constant extra space.
**Cons:** The logic can be subtle and tricky to get right, especially the conditions for deciding which element to modify.
### Explanation
We can solve this problem efficiently in a single pass. The idea is to iterate through the array, keeping track of the number of modifications made. If the array is already non-decreasing, we'll complete the pass without any modifications and return `true`.

When we encounter the first violation, where `nums[i] > nums[i+1]`, we increment our modification count. If we ever find a second violation, we know it's impossible to fix with just one change, so we can return `false` immediately.

With the first violation at index `i`, we must decide whether to lower `nums[i]` or raise `nums[i+1]`. Lowering `nums[i]` is generally preferable because it results in smaller values, which are less likely to conflict with subsequent elements. We can lower `nums[i]` (e.g., to `nums[i+1]`) if this change doesn't violate the order with the preceding element, `nums[i-1]`. This is valid if `i == 0` (no preceding element) or if `nums[i-1] <= nums[i+1]`.

If we cannot lower `nums[i]` (because `nums[i-1] > nums[i+1]`), our only alternative is to raise `nums[i+1]` (e.g., to `nums[i]`). We perform this modification in the array and continue our scan. If this change leads to another violation later on, our modification counter will catch it.

If we finish the loop, it means we have made at most one valid modification, so the array can become non-decreasing. Thus, we return `true`.

```java
class Solution {
    public boolean checkPossibility(int[] nums) {
        int modifications = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                modifications++;
                if (modifications > 1) {
                    return false;
                }
                
                // We found a dip: nums[i] > nums[i+1].
                // Check if lowering nums[i] is possible.
                // This is possible if there's no element before it (i=0)
                // or if the element before it is smaller than or equal to nums[i+1].
                if (i > 0 && nums[i - 1] > nums[i + 1]) {
                    // Lowering nums[i] is not possible as it would break the order with nums[i-1].
                    // So, we must raise nums[i+1].
                    nums[i + 1] = nums[i];
                } 
                // Else, lowering nums[i] is the preferred option. We can imagine
                // nums[i] is changed to nums[i+1]. We don't need to actually modify
                // nums[i] because it won't be checked again in the loop.
            }
        }
        return true;
    }
}
```
### Algorithm
1. Initialize a counter `modifications = 0`.
2. Iterate through the array from `i = 0` to `n-2`.
3. If `nums[i] <= nums[i+1]`, the order is correct, so continue.
4. If `nums[i] > nums[i+1]`, a violation is found.
   a. Increment `modifications`. If `modifications` becomes greater than 1, return `false` immediately.
   b. We must fix this violation. We have two choices: lower `nums[i]` or raise `nums[i+1]`.
   c. Check if lowering `nums[i]` is a valid move. This is possible if it doesn't create a new violation with `nums[i-1]`. The condition is `i == 0 || nums[i-1] <= nums[i+1]`.
   d. If lowering `nums[i]` is not possible (the condition in `4c` is false), we must attempt to raise `nums[i+1]`. We do this by setting `nums[i+1] = nums[i]`. This modification is carried forward for subsequent checks in the loop.
   e. If lowering `nums[i]` is possible, we can conceptually proceed as if `nums[i]` was lowered. We don't need to actually modify the array in this case, as the original `nums[i]` value won't be used in future comparisons.
5. If the loop completes, it means we encountered at most one fixable violation. Return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean checkPossibility(int[] nums) {
    for (int i = 0; i < nums.length - 1; ++i) {
      int a = nums[i], b = nums[i + 1];
      if (a > b) {
        nums[i] = b;
        if (isSorted(nums)) {
          return true;
        }
        nums[i] = a;
        nums[i + 1] = a;
        return isSorted(nums);
      }
    }
    return true;
  }
private
  boolean isSorted(int[] nums) {
    for (int i = 0; i < nums.length - 1; ++i) {
      if (nums[i] > nums[i + 1]) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool checkPossibility(vector<int> &nums) {
    int n = nums.size();
    for (int i = 0; i < n - 1; ++i) {
      int a = nums[i], b = nums[i + 1];
      if (a > b) {
        nums[i] = b;
        if (is_sorted(nums.begin(), nums.end())) {
          return true;
        }
        nums[i] = a;
        nums[i + 1] = a;
        return is_sorted(nums.begin(), nums.end());
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def checkPossibility(self, nums: List[int]) -> bool: def is_sorted(nums: List[int]) -> bool: return all(a <= b for a, b in pairwise(nums)) n = len(nums) for i in range(n - 1): a, b = nums[i], nums[i + 1] if a > b: nums[i] = b if is_sorted(nums): return True nums[i] = nums[i + 1] = a return is_sorted(nums) return True

```