O(n) time C++ solution with explanation, no need to modify the array


  • 1
    F

    The idea is that we keep the count of invalid pair where a[i] < a[i-1], once count equals 2, then definitely, we can not change this array to non-decreasing in at most 1 step.

    If there only 1 invalid pair, if i=1 or i = nums.size()-1, then it is possible to change the array to non-decreasing in 1 step. When i equals other value, we have two choice to make array non-decreasing:

    • Choice 1
      Increase a[i] to at least the value of a[i-1], but we have to make sure a[i-1] <= a[i+1]
    • Choice 2
      Decrease a[i-1] to at least the value of a[i], also we have to check if a[i] >= a[i-2]

    If the above two choices are all invalid, the we must return false;

    the code below is written according to this idea

    if (nums.size() <= 2) {return true;}
            int count = 0;
            for (int i = 1; i < nums.size(); ++i){
                if (nums[i] < nums[i-1]){
                    ++count;
                    if (count == 2) return false;
                    if (i != 1 and i != nums.size()-1){
                        if (nums[i-1] > nums[i+1] and nums[i] < nums[i-2]){
                            return false;
                        }
                    }
                }
            }
            return true;
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.