[LeetCode] Problem 665 - Non-decreasing Array

Posted on | In ,

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

No.1

Input: [4,2,3]

Output: True

Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

No.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].

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean checkPossibility(int[] nums) {
    int count = 1;

    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < nums[i - 1]) {
            if (i >= 2 && nums[i] < nums[i - 2])
                nums[i] = nums[i - 1];
            else 
                nums[i - 1] = nums[i];
            
            if (--count < 0)
                return false;
        }
    }

    return true;
}