Description
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
Solutions
Solution 1
PythonJavaC++GoTypeScript
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
def is_sorted(nums: List[int]) -> bool:
return all(a <= b for a, b in pairwise(nums))
n = len(nums)
for i in range(n - 1):
a, b = nums[i], nums[i + 1]
if a > b:
nums[i] = b
if is_sorted(nums):
return True
nums[i] = nums[i + 1] = a
return is_sorted(nums)
return True(code-box)
class Solution {
public boolean checkPossibility(int[] nums) {
for (int i = 0; i < nums.length - 1; ++i) {
int a = nums[i], b = nums[i + 1];
if (a > b) {
nums[i] = b;
if (isSorted(nums)) {
return true;
}
nums[i] = a;
nums[i + 1] = a;
return isSorted(nums);
}
}
return true;
}
private boolean isSorted(int[] nums) {
for (int i = 0; i < nums.length - 1; ++i) {
if (nums[i] > nums[i + 1]) {
return false;
}
}
return true;
}
}(code-box)
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n - 1; ++i) {
int a = nums[i], b = nums[i + 1];
if (a > b) {
nums[i] = b;
if (is_sorted(nums.begin(), nums.end())) {
return true;
}
nums[i] = a;
nums[i + 1] = a;
return is_sorted(nums.begin(), nums.end());
}
}
return true;
}
};(code-box)
func checkPossibility(nums []int) bool {
isSorted := func(nums []int) bool {
for i, b := range nums[1:] {
if nums[i] > b {
return false
}
}
return true
}
for i := 0; i < len(nums)-1; i++ {
a, b := nums[i], nums[i+1]
if a > b {
nums[i] = b
if isSorted(nums) {
return true
}
nums[i] = a
nums[i+1] = a
return isSorted(nums)
}
}
return true
}(code-box)
function checkPossibility(nums: number[]): boolean {
const isSorted = (nums: number[]) => {
for (let i = 0; i < nums.length - 1; ++i) {
if (nums[i] > nums[i + 1]) {
return false;
}
}
return true;
};
for (let i = 0; i < nums.length - 1; ++i) {
const a = nums[i],
b = nums[i + 1];
if (a > b) {
nums[i] = b;
if (isSorted(nums)) {
return true;
}
nums[i] = a;
nums[i + 1] = a;
return isSorted(nums);
}
}
return true;
}(code-box)
