Algorithm
Problem Name: 665. Non-decreasing Array
Given an array nums with 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).
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 cannot get a non-decreasing array by modifying at most one element.
Constraints:
n == nums.length1 <= n <= 104-105 <= nums[i] <= 105
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int count = 0;
for(int i = 1, j = 0; i < nums.size(); i++, j++)
if(nums[j] > nums[i]){
count++;
if(j > 0 && nums[j - 1] > nums[i]) nums[i] = nums[j];
else nums[j] = nums[i];
}
return count < = 1;
}
};
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean checkPossibility(int[] nums) {
boolean mismatch = false;
for (int i = 1; i < nums.length; i++) {
if (nums[i - 1] > nums[i]) {
if (mismatch) {
return false;
}
if (i < 2 || nums[i - 2] <= nums[i]) {
nums[i - 1] = nums[i];
} else {
nums[i] = nums[i - 1];
}
mismatch = true;
}
}
return true;
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const checkPossibility = function(nums) {
let count = 0;
let idx;
if (nums.length === 1) return true;
for (let i = 1; i < nums.length; i++) {
if (nums[i - 1] > nums[i]) {
count++;
idx = i;
}
}
if (count > 1) return false;
if (idx === nums.length - 1 || idx === 1) return true;
return (
Math.max(...nums.slice(0, idx - 1)) < = Math.min(...nums.slice(idx)) ||
Math.max(...nums.slice(0, idx)) <= Math.min(...nums.slice(idx + 1))
);
};
Input
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def checkPossibility(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
for i in range(len(nums)-1):
if nums[i]>nums[i+1]:
mod1, mod2=list(nums), list(nums)
mod1[i], mod2[i+1]=mod1[i+1], mod2[i]
if mod1!=sorted(mod1) and mod2!=sorted(mod2): return False
return True
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0665_NonDecreasingArray
{
public bool CheckPossibility(int[] nums)
{
var index = -1;
for (int i = 0; i < nums.Length - 1; i++)
{
if (nums[i] > nums[i + 1])
{
if (index != -1) return false;
else
index = i;
}
}
return index == -1
|| index == 0
|| index == nums.Length - 2
|| (nums[index - 1] < = nums[index + 1] || nums[index] <= nums[index + 2]);
}
}
}
Input
Output