Approach #1: Brute Force [Time Limit Exceeded]
Intuition
For the given array A
, if we are changing at most one element A[i]
, we should change A[i]
to A[i1]
, as it would be guaranteed that A[i1] <= A[i]
, and A[i]
would be the smallest possible to try and achieve A[i] <= A[i+1]
.
Algorithm
For each possible change A[i]
, check if the sequence is monotone increasing. We'll modify new
, a copy of the array A
.
Python
class Solution(object):
def checkPossibility(self, A):
def monotone_increasing(arr):
for i in range(len(arr)  1):
if arr[i] > arr[i+1]:
return False
return True
for i in range(len(A)):
old_ai = A[i]
A[i] = A[i1] if i > 0 else float('inf')
if monotone_increasing(A):
return True
A[i] = old_ai
return False
Java
class Solution {
private boolean monotoneIncreasing(int[] nums) {
for (int i = 0; i < nums.length  1; i++) {
if (nums[i] > nums[i+1]) return false;
}
return true;
}
public boolean checkPossibility(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int old = nums[i];
nums[i] = i > 0 ? nums[i1] : Integer.MIN_VALUE;
if (monotoneIncreasing(nums)) return true;
nums[i] = old;
}
return false;
}
}
Complexity Analysis

Time Complexity: Let $$N$$ be the length of the given array. For each element
A[i]
, we check if some sequence is monotone increasing, which takes $$O(N)$$ steps. In total, this is a complexity of $$O(N^2)$$. 
Space Complexity: Only $$O(1)$$ additional space was used.
Approach #2: Reduce to Smaller Problem [Accepted]
Intuition
If A[0] <= A[1] <= A[2]
, then we may remove A[0]
without changing the answer. Similarly, if A[len(A)3] <= A[len(A)2] <= A[len(A)1]
, we may remove A[len(A)1]
without changing the answer.
If the problem is solvable, then after these removals, very few numbers will remain.
Algorithm
Consider the interval [i, j]
corresponding to the subarray [A[i], A[i+1], ..., A[j]]
. When A[i] <= A[i+1] <= A[i+2]
, we know we do not need to modify A[i]
, and we can consider solving the problem on the interval [i+1, j]
instead. We use a similar approach for j
.
Afterwards, with the length of the interval under consideration being j  i + 1
, if the interval has size 2 or less, then we did not find any problem. If our interval under consideration has 5 or more elements, then there are two disjoint problems that cannot be fixed with one replacement. Otherwise, our problem size is now at most 4 elements, which we can easily brute force.
Python
class Solution(object):
def checkPossibility(self, A):
def brute_force(A):
# As in Approach #1
i, j = 0, len(A)  1
while i+2 < len(A) and A[i] <= A[i+1] <= A[i+2]:
i += 1
while j2 >= 0 and A[j2] <= A[j1] <= A[j]:
j = 1
if j  i + 1 <= 2:
return True
if j  i + 1 >= 5:
return False
return brute_force(A[i: j+1])
Java
class Solution {
private boolean monotoneIncreasing(int[] nums) {
// As in Approach #1
}
public boolean bruteForce(int[] nums) {
// As in Approach #1
}
public boolean checkPossibility(int[] nums) {
int i = 0, j = nums.length  1;
while (i+2 < nums.length && nums[i] <= nums[i+1] && nums[i+1] <= nums[i+2]) i++;
while (j2 >= 0 && nums[j2] <= nums[j1] && nums[j1] <= nums[j]) j;
if (ji + 1 <= 2) return true;
if (ji + 1 >= 5) return false;
return bruteForce(Arrays.copyOfRange(nums, i, j+1));
}
}
Complexity Analysis

Time Complexity: Let $$N$$ be the length of the given array. Our pointers
i
andj
move at most $$O(N)$$ times. Our brute force is constant time as there are at most 4 elements in the array. Hence, the complexity is $$O(N)$$. 
Space Complexity: The extra array
A[i: j+1]
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 $$O(1)$$.
Approach #3: Locate and Analyze Problem Index [Accepted]
Intuition
Consider all indices p
for which A[p] > A[p+1]
. 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 A
to be monotone increasing.
At the problem index p
, we only care about the surrounding elements. Thus, immediately the problem is reduced to a very small size that can be analyzed by casework.
Algorithm
As before, let p
be the unique problem index for which A[p] > A[p+1]
. If this is not unique or doesn't exist, the answer is False
or True
respectively. We analyze cases:
 If
p = 0
, then we could make the array good by settingA[p] = A[p+1]
.  If
p = len(A)  2
, then we could make the array good by settingA[p+1] = A[p]
.  Otherwise,
A[p1], A[p], A[p+1], A[p+2]
all exist, and: We could change
A[p]
to be betweenA[p1]
andA[p+1]
if possible, or;  We could change
A[p+1]
to be betweenA[p]
andA[p+2]
if possible.
 We could change
Python
class Solution(object):
def checkPossibility(self, A):
p = None
for i in xrange(len(A)  1):
if A[i] > A[i+1]:
if p is not None:
return False
p = i
return (p is None or p == 0 or p == len(A)2 or
A[p1] <= A[p+1] or A[p] <= A[p+2])
Java
class Solution {
public boolean checkPossibility(int[] nums) {
int p = 1;
for (int i = 0; i < nums.length  1; i++) {
if (nums[i] > nums[i+1]) {
if (p >= 0) return false;
p = i;
}
}
return (p == 1  p == 0  p == nums.length  2 
nums[p1] <= nums[p+1]  nums[p] <= nums[p+2]);
}
}
Complexity Analysis

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

Space Complexity: We only use
p
,i
, and the answer itself as additional space. The additional space complexity is $$O(1)$$.