665. Non-decreasing Array
1. Description
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).
2. Example
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 modify at most one element.
3. Note
- 1 <= n <= 10$^{4}$
- -10$^{5}$ <= nums[i] <= 10$^{5}$
4. Solutions
Array
n = i_nums.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution
{
public:
// bool checkPossibility(vector<int>& nums)
bool checkPossibility(vector<int> &i_nums)
{
int invalidIndex = -1;
for(int i = 1; i < i_nums.size(); i++)
{
if(i_nums[i - 1] > i_nums[i])
{
if(invalidIndex != -1) return false;
invalidIndex = i - 1;
}
}
// invalidIndex is the index of the first number of a invalid pair
// if invalidIndex == -1, there is no invalid pair at all, the array is valid
// if invalidIndex == 0, we could set the first number in the pair to the second number, vice versa
// if invalidIndex == i_nums.size() - 2, we could set the first number in the pair to the second number, vice versa
// if i_nums[invalidIndex - 1] <= i_nums[invalidIndex + 1], we could set the first number in the pair to the second number
// if i_nums[invalidIndex] <= i_nums[invalidIndex + 2], we could set the second number in the pair to the first number
return (invalidIndex == -1 || invalidIndex == 0 || invalidIndex == i_nums.size() - 2 || i_nums[invalidIndex - 1] <= i_nums[invalidIndex + 1] || i_nums[invalidIndex] <= i_nums[invalidIndex + 2]);
}
};