# Solution by awice

• #### 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[i-1]`, as it would be guaranteed that `A[i-1] <= 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[i-1] 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[i-1] : 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 j-2 >= 0 and A[j-2] <= A[j-1] <= 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 (j-2 >= 0 && nums[j-2] <= nums[j-1] && nums[j-1] <= nums[j]) j--;

if (j-i + 1 <= 2) return true;
if (j-i + 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` and `j` 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 setting `A[p] = A[p+1]`.
• If `p = len(A) - 2`, then we could make the array good by setting `A[p+1] = A[p]`.
• Otherwise, `A[p-1], A[p], A[p+1], A[p+2]` all exist, and:
• We could change `A[p]` to be between `A[p-1]` and `A[p+1]` if possible, or;
• We could change `A[p+1]` to be between `A[p]` and `A[p+2]` if possible.

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[p-1] <= 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[p-1] <= 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)\$\$.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.