## 665. Non-decreasing Array

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].

b'
\n\n

## Solution

\n
\n

#### Approach #1: Brute Force [Time Limit Exceeded]

\n

Intuition

\n

For the given array , if we are changing at most one element , we should change to , as it would be guaranteed that , and would be the smallest possible to try and achieve .

\n

Algorithm

\n

For each possible change , check if the sequence is monotone increasing. We\'ll modify , a copy of the array .

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: Let be the length of the given array. For each element , we check if some sequence is monotone increasing, which takes steps. In total, this is a complexity of .

\n
• \n
• \n

Space Complexity: To hold our array , we need space.

\n
• \n
\n
\n

#### Approach #2: Reduce to Smaller Problem [Accepted]

\n

Intuition

\n

If , then we may remove without changing the answer. Similarly, if , we may remove without changing the answer.

\n

If the problem is solvable, then after these removals, very few numbers will remain.

\n

Algorithm

\n

Consider the interval corresponding to the subarray . When , we know we do not need to modify , and we can consider solving the problem on the interval instead. We use a similar approach for .

\n

Afterwards, with the length of the interval under consideration being , if the interval has size 2 or less, then we did not find any problem.

\n

If our interval under consideration has 5 or more elements, then there are two disjoint problems that cannot be fixed with one replacement.

\n

Otherwise, our problem size is now at most 4 elements, which we can easily brute force.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: Let be the length of the given array. Our pointers and move at most times. Our brute force is constant time as there are at most 4 elements in the array. Hence, the complexity is .

\n
• \n
• \n

Space Complexity: The extra array only has at most 4 elements, so it is constant space, and so is the space used by our auxillary brute force algorithm. In total, the space complexity is .

\n
• \n
\n
\n

#### Approach #3: Locate and Analyze Problem Index [Accepted]

\n

Intuition

\n

Consider all indices for which . If there are zero, the answer is True. If there are 2 or more, the answer is False, as more than one element of the array must be changed for to be monotone increasing.

\n

At the problem index , we only care about the surrounding elements. Thus, immediately the problem is reduced to a very small size that can be analyzed by casework.

\n

Algorithm

\n

As before, let be the unique problem index for which . If this is not unique or doesn\'t exist, the answer is False or True respectively. We analyze the following cases:

\n
\n
• If , then we could make the array good by setting .
• \n
• If , then we could make the array good by setting .
• \n
• Otherwise, all exist, and:
\n
• We could change to be between and if possible, or;
• \n
• We could change to be between and if possible.
• \n
\n
• \n
\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: Let be the length of the given array. We loop through the array once, so our time complexity is .

\n
• \n
• \n

Space Complexity: We only use and , and the answer itself as the additional space. The additional space complexity is .

\n
• \n
\n
\n

Analysis written by: @awice

\n
'