Given an array
n integers, your task is to check if it could become non-decreasing by modifying at most one 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).
Input: nums = [4,2,3]
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
Input: nums = [4,2,1]
Explanation: You can't get a non-decreasing array by modify at most one element.
We are going to solve this problem greedily. We can modify at array at max 1 time so that it becomes a non-decreasing array.
To achieve that, we have to take care of few things.
- When modifying the number at index
i-1, we need to consider elements at
- Need to make sure that the array satisfies the conditions even after modifications are made.
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 the first as long as the number at position
i-2is equal or lower than the current element(index
i-2is valid. If we can’t then go for the second condition. We give priority to the first case.
Check the code below.
Check the whole repository for more leetcode solutions.