665.Non-decreasing Array

Posted on | In

665. Non-decreasing Array

Given an array 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 array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:
Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
Example 2:
Input: [4,2,1]
Output: False
Explanation: You can’t get a non-decreasing array by modify at most one element.
Note: The n belongs to [1, 10,000].

Test cases

1
2
3
4
5
6
7
[2,4,2,3]
[3,4,2,3]
[3,3,4,2]
[3,3,4,2,3]
[3,3,4,2,4]
[1,2,4,5,3]
[1,5,4,6,7,10,8,9]

Solution 1: accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean checkPossibility(int[] nums) {
    int len = nums.length;
    boolean once = false;
    for (int i = 1; i < len; i++) {
        if (nums[i] < nums[i - 1]) {
            if (once) {
                return false;
            } else if (i - 2 >= 0 && i < len - 1) {
                if (nums[i - 2] > nums[i] && nums[i + 1] < nums[i - 1])
                    return false;
            }
            once = true;
        }
    }
    return true;
}