Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.
We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).
Example 1:
Input: nums = [4,2,3] Output: true Explanation: You could modify the first 4 to 1 to get a non-decreasing array. Example 2:
Input: nums = [4,2,1] Output: false Explanation: You can't get a non-decreasing array by modifying at most one element.
Constraints:
1 <= n <= 10 ^ 4 - 10 ^ 5 <= nums[i] <= 10 ^ 5
public class Solution {
public bool CheckPossibility(int[] nums) {
int modify = 0;
for(int i=1;i<nums.Length;i++){
if(nums[i]<nums[i-1]){
modify++;
if(i-2<0||nums[i-2]<=nums[i]){
nums[i-1]=nums[i];
}
else{
nums[i]=nums[i-1];
}
}
}
return modify<=1;
}
}Time Complexity: O(n)
Space Complexity: O(1)
Explanation:
The problem requires that every number has to be equal or greater than the previous number. If we encounter a failing condition where the number is not greater or equal to the previous (smaller than previous) we need to make a correction. Correction can be made in either of two ways:
Make the previous number smaller or equal to the current number Make the current number equal to the previous number We can do (1) as long as the number at position i-2 is equal or lower than the current element. (if i-2 is valid) In case 1 below we can do this at (3) (i = 2) as the element 1 (i = 0) fulfills 1 <= 3. We can replace 7 with 3. However, this cannot be done in case 2 as 4 <= 3 does not satisfy.
Correction with technique (1) takes priority as there is no risk in lowering the value but there is a risk associated if the value is increased. (Consider a scenario in case 1 if we replace 3 with 7, it will fail to satisfy the condition for the last element)
We have to make corrections with (2) if we cannot achieve it by (1). In which case we increase the value of the current element by matching the previous element. In case 2, we replace 3 with 7.
Also, we only compare condition with the previous element only because as we move forward we know the previous numbers are already validated.
Case 1: 7 /\ 4 / \ / / \/ / 3 1
Case 2: 9 / 7 / /\ / / \/ / 3 4
