Given an array with
n integers, your task is to check if it could become non-decreasing by modifying at most
We define an array is non-decreasing if
array[i] <= array[i + 1] holds for every
i (1 <= i < n).
Input: [4,2,3] Output: True Explanation: You could modify the first
1to get a non-decreasing array.
Input: [4,2,1] Output: False Explanation: You can't get a non-decreasing array by modify at most one element.
n belongs to [1, 10,000].
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 .\n
For each possible change , check if the sequence is monotone increasing. We\'ll modify , a copy of the array .\n\n
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 .\n
Space Complexity: To hold our array , we need space.\n
If , then we may remove without changing the answer. Similarly, if , we may remove without changing the answer.\n
If the problem is solvable, then after these removals, very few numbers will remain.\n
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 .\n
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.\n
If our interval under consideration has 5 or more elements, then there are two disjoint problems that cannot be fixed with one replacement.\n
Otherwise, our problem size is now at most 4 elements, which we can easily brute force.\n\n
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 .\n
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 .\n
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.\n
As before, let be the unique problem index for which . If this is not unique or doesn\'t exist, the answer is
True respectively. We analyze the following cases:
Time Complexity: Let be the length of the given array. We loop through the array once, so our time complexity is .\n
Space Complexity: We only use and , and the answer itself as the additional space. The additional space complexity is .\n
Analysis written by: @awice\n