Solution
Approach #1: Brute Force [Time Limit Exceeded]
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 .
Algorithm
For each possible change , check if the sequence is monotone increasing. We'll modify , a copy of the array .
Complexity Analysis

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 .

Space Complexity: To hold our array , we need space.
Approach #2: Reduce to Smaller Problem [Accepted]
Intuition
If , then we may remove without changing the answer. Similarly, if , we may remove without changing the answer.
If the problem is solvable, then after these removals, very few numbers will remain.
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 .
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.
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.
Complexity Analysis

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 .

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 .
Approach #3: Locate and Analyze Problem Index [Accepted]
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.
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:
 If , then we could make the array good by setting .
 If , then we could make the array good by setting .
 Otherwise, all exist, and:
 We could change to be between and if possible, or;
 We could change to be between and if possible.
Complexity Analysis

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

Space Complexity: We only use and , and the answer itself as the additional space. The additional space complexity is .
Analysis written by: @awice