easy to understand C++ without modifying array


  • 0
    D

    count1 is the number of modifications needed for changing the higher value with lower index. for example: 1,2,3,2,4. when 3>2, you have to modify 3 to 2 to keep one modification.
    count2 is the number of modifications needed for changing the lower value with higher index. for example: 1,2.3,1,4, when 3>1, you have to modify 1 to (3 or 4) to keep only on modification.

    the algorithm below is to test for both cases, and return true if any type of modification works, and false if neither way works.

        bool checkPossibility(vector<int>& nums) {
            int count1 = 0, count2 = 0;
            for(int i = 1; i<nums.size() && (count1<2 || count2<2); ++i)
            {
                if(nums[i-1] > nums[i])
                {
                    count1++;
                    count1 += (i > 1) && nums[i-2] > nums[i];
                    count2++;
                    count2 += (i+1 < nums.size()) && nums[i+1] < nums[i-1];
                }
            }
            return count1 < 2 || count2 < 2;
        }
    
    

Log in to reply
 

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