This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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:TrueExplanation:You could modify the first`4`

to`1`

to get a non-decreasing array.

**Example 2:**

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

**Note:**
The `n`

belongs to [1, 10,000].

b'

\n## Solution

\n

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

\n

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

\n

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

\n

\n

'
\n\n

\n\n

**Intuition**

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**

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

**Intuition**

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

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

\n**Algorithm**

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 .

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

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

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

\n\n**Complexity Analysis**

- \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

**Intuition**

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.

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**

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

**Complexity Analysis**

- \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

Analysis written by: @awice

\n