[C]: Simple solution, logic will be easy if you check elements from the end..


  • 0
    S
    1. Check elements from end of the array.
    2. When condition fails. There are three cases to handle,
      Case 1: 1 2 3 4 5 1 ---> Condition beaks while comparing ( 5, 1). Modify last element 1 to 5.
      Case 2: 1 2 3 4 0 6 ----> Condition breaks while comparing (4,0). Modify 0 to 4.
      Case 3: 1 2 3 6 4 5 ---> Condition breaks while comparing (6,4). Modify 6 to 4 ( because last seen element is 5, only possible solution:: change 6 to 4)

    Note: We can use same logic without modifying the element also.

    bool checkPossibility(int* nums, int numsSize) {
        int prev_element = INT_MAX, i, count = 0;
        
        if ( numsSize == 0 )
            return false;
        
        if ( numsSize == 1 )
            return true;
        
        for( i = (numsSize-1) ; i > 0 ; i--)
        {      
            if( nums[i-1] > nums[i])
            {
                if( ++count == 2)
                    return false;
                
                if( nums[i-1] > prev_element)
                    nums[i-1] = nums[i];
                else
                    nums[i] = nums[i-1];
             }
            prev_element = nums[i];
        }
        return true;
    }
    

Log in to reply
 

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