Solution

Approach #1: Brute Force [Time Limit Exceeded]

Intuition

For the given array $$\\text{A}$$ , if we are changing at most one element $$\\text{A[i]}$$ , we should change $$\\text{A[i]}$$ to $$\\text{A[i-1]}$$ , as it would be guaranteed that $$\\text{A[i-1]} ≤ \\text{A[i]}$$ , and $$\\text{A[i]}$$ would be the smallest possible to try and achieve $$\\text{A[i]} ≤ \\text{A[i+1]}$$ .

Algorithm

For each possible change $$\\text{A[i]}$$ , check if the sequence is monotone increasing. We\'ll modify $$\\text{new}$$ , a copy of the array $$\\text{A}$$ .

Complexity Analysis

\n
• \n

  Time Complexity: Let $$N$$ be the length of the given array. For each element $$\\text{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)$$ .

  \n
\n
• \n

  Space Complexity: To hold our array $$\\text{new}$$ , we need $$O(N)$$ space.

  \n
\n

Approach #2: Reduce to Smaller Problem [Accepted]

Intuition

If $$\\text{A[0]} ≤ \\text{A[1]} ≤ \\text{A[2]}$$ , then we may remove $$\\text{A[0]}$$ without changing the answer. Similarly, if $$\\text{A}\\big[\\text{len(A)-3}\\big] ≤ \\text{A}\\big[\\text{len(A)-2}\\big] ≤ \\text{A}\\big[\\text{len(A)-1}\\big]$$ , we may remove $$\\text{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 $$\\text{[i, j]}$$ corresponding to the subarray $$\\big[\\text{A[i], A[i+1], ..., A[j]}\\big]$$ . When $$\\text{A[i]} ≤ \\text{A[i+1]} ≤ \\text{A[i+2]}$$ , we know we do not need to modify $$\\text{A[i]}$$ , and we can consider solving the problem on the interval $$\\text{[i+1, j]}$$ instead. We use a similar approach for $$j$$ .

Afterwards, with the length of the interval under consideration being $$\\text{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.

Complexity Analysis

\n
• \n

  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)$$ .

  \n
\n
• \n

  Space Complexity: The extra array $$\\text{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)$$ .

  \n
\n

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

Intuition

Consider all indices $$p$$ for which $$\\text{A[p]} > \\text{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 $$\\text{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 $$\\text{A[p]} > \\text{A[p+1]}$$ . If this is not unique or doesn\'t exist, the answer is False or True respectively. We analyze the following cases:

\n
• If $$\\text{p = 0}$$ , then we could make the array good by setting $$\\text{A[p] = A[p+1]}$$ .
\n
• If $$\\text{p = len(A) - 2}$$ , then we could make the array good by setting $$\\text{A[p+1] = A[p]}$$ .
\n
• Otherwise, $$\\text{A[p-1], A[p], A[p+1], A[p+2]}$$ all exist, and:
  \n
  • We could change $$\\text{A[p]}$$ to be between $$\\text{A[p-1]}$$ and $$\\text{A[p+1]}$$ if possible, or;
  \n
  • We could change $$\\text{A[p+1]}$$ to be between $$\\text{A[p]}$$ and $$\\text{A[p+2]}$$ if possible.
  \n
  \n
\n

Complexity Analysis

\n
• \n

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

  \n
\n
• \n

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

  \n
\n

Analysis written by: @awice