Simple C++ 18 lines withnot modifying input


  • 0
    M

    Use flag to see if you have modified before. The problem is when nums[i]<nums[i-1], you need to choose to modify nums[i-1] or nums[i] (preferably nums[i-1] since we are moving forward to i+1 in next loop).

    If it is the first time violation, consider 4 cases in order

    1. if i==1, then we definitely modify nums[i-1] since modifying nums[0] will not affect any prior cells.
    2. else if i==n-1, then it does not matter if we modify nums[i-1] or nums[i]. Whichever we will return true.
    3. else if nums[i] >= nums[i-2], modify nums[i-1] to be nums[i]. We do not need to really modify anything since we move on to i+1 next loop and nums[i-1] does not matter anymore
    4. else if nums[i-1] <= nums[i+1], modify nums[i] to become nums[i-1]. We do not need to really modify anything here as well since the purpose of modifying nums[i] is to make nums[i+1]>=nums[i]. However, nums[i]<nums[i-1] already so we do not need to modify nums[i] to be nums[i-1].

    Since we have nums[i]<nums[i-1] already, if the above 4 cases all fail, it means we get another violation immediately so we return false. Otherwise, we just count this one violation and move forward without the need to modify anything.

    class Solution {
    public:
        bool checkPossibility(vector<int>& nums) {
            if(nums.size()<=1) return true;
            bool flag=false;
            for(int i=1; i<nums.size(); i++) {
                if(nums[i]<nums[i-1]) {
                    if(!flag) { // first violation
                        flag=true; 
                        if(i!=1 && i!=nums.size()-1 && nums[i]<nums[i-2] && nums[i-1]>nums[i+1])  
                            return false; // immediate violation after the first
                    }
                    else return false; // second violation
                }
            }
            return true;
        }
    };
    

Log in to reply
 

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