Very easy to understand C++


  • 5

    "NON-DECREASING" is a double negative. This is the same as an array sorted in ascending order where nums[i] <= nums[i+1].

    Find the first exception to this rule where nums[i] > nums[i+1],
    then see if the rest of the array is sorted in ascending order ( without nums[i] ) XOR ( without nums[i+1] ).

    class Solution {
    public:
        bool checkPossibility(vector<int>& nums) {
            for (int i=0; i < nums.size()-1; i++){
                if (nums[i] > nums[i+1]){
                    
                    int temp = nums[i];
                    //
                    // "erase" nums[i], then check if nums is sorted without nums[i]
                    //
                    nums[i] = nums[i+1];
                    if (is_sorted(nums.begin(), nums.end())) { return true; }
                    
                    //
                    // "erase" nums[i+1], then check if nums is sorted without nums[i+1]
                    //
                    nums[i+1] = nums[i] = temp;
                    if (is_sorted(nums.begin(), nums.end())) { return true; }
                    
                    //
                    // nums is NOT sorted (without nums[i] XOR without nums[i+1])
                    //
                    return false;
                }
            }
            return true;
        }
    };
    

  • 1
    S

    @claytonjwong very smart.


  • 1
    X

    Same idea:

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

  • 1
    A

    It is a really good idea!


Log in to reply
 

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