Non-decreasing Array

Description

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

Solutions

My solution

Idea: nums[0..i] and nums[j..n-1] are longest non-decreasing sequences starting at nums[0] and ending at nums[n-1], respectively.

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int i = 0, n = nums.size();
        while(i + 1 < n && nums[i] <= nums[i + 1]) ++i;

        // i == n - 1, the whole array is non-decreasing
        // i == n - 2, we can change the last element to make the array non-decreasing.
        if(i >= n - 2) return true;
        int j = n - 1;

        // no need to check j > 0 because
        // nums[i] > nums[i + 1]
        // so the while loop must terminate
        while(nums[j - 1] <= nums[j]) --j;
        
        // if j - i > 1, at least two reverse pairs
        // i.e., (nums[i], nums[i + 1]) and (nums[j - 1], nums[j])
        if(j - i > 1) return false;

        // i + 1 == j
        // only one reverse pair
        // check if it's possible to change either nums[i] or nums[j]
        // to make the array non-decreasing
        return i == 0 || nums[i - 1] <= nums[j] || nums[i] <= nums[j + 1];
    }
};

Solution 1

Explanation: if there is a reverse pair (nums[i], nums[i + 1]). We need to change either nums[i] or nums[i + 1]. If i > 0 && nums[i - 1] > nums[i + 1], we must change nums[i + 1]. Otherwise, we can change either nums[i] or nums[i + 1]. But we prefer changing nums[i] because if we can change nums[i + 1] (i.e., let nums[i + 1] = nums[i]) to make the array non-decreasing, then we can also change nums[i] (i.e., let nums[i] = nums[i + 1]) to make the array non-decreasing (the other direction is not true).

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int count = 0;
        // we can use some variable to remember the modified element
        // if we don't want the array to be changed when the function returns.
        //int idx = -1, val = -1;
        for(int i = 0; i + 1 < nums.size(); ++i){
            if(nums[i] > nums[i + 1]){
                if(++count > 1)
                    return false;
                // if i == 0 || nums[i - 1] <= nums[i + 1], we can change nums[i] to nums[i + 1]
                // otherwise, we have to change nums[i + 1] to nums[i]
                if(i > 0 && nums[i - 1] > nums[i + 1]){
                    //idx = i + 1;
                    //val = nums[i + 1];
                    nums[i + 1] = nums[i];
                }
            }
        }
        //if(idx != -1) nums[idx] = val;
        return true;
    }
};

Solution 2

Credit: https://leetcode.com/problems/non-decreasing-array/discuss/106842/The-easiest-python-solution....

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int count = 0;
        int n = nums.size();
        for(int i = 0; i + 1 < n; ++i){
            if(nums[i] > nums[i + 1]){
                ++count;
                if(count > 1 || i > 0 && i + 2 < n && nums[i - 1] > nums[i + 1] && nums[i] > nums[i + 2])
                    return false;
            }
        }
        return true;
    }
};