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