[Java/C++] Simple greedy like solution with explanation


  • 26

    This problem is like a greedy problem. When you find nums[i-1] > nums[i] for some i, you will prefer to change nums[i-1]'s value, since a larger nums[i] will give you more risks that you get inversion errors after position i. But, if you also find nums[i-2] > nums[i], then you have to change nums[i]'s value instead, or else you need to change both of nums[i-2]'s and nums[i-1]'s values.

    Java version:

     public boolean checkPossibility(int[] nums) {
            int cnt = 0;                                                                    //the number of changes
            for(int i = 1; i < nums.length && cnt<=1 ; i++){
                if(nums[i-1] > nums[i]){
                    cnt++;
                    if(i-2<0 || nums[i-2] <= nums[i])nums[i-1] = nums[i];                    //modify nums[i-1] of a priority
                    else nums[i] = nums[i-1];                                                //have to modify nums[i]
                }
            }
            return cnt<=1; 
        }
    

    C++ version:

    bool checkPossibility(vector<int>& nums) {
            int cnt = 0;                                                                    //the number of changes
            for(int i = 1; i < nums.size() && cnt<=1 ; i++){
                if(nums[i-1] > nums[i]){
                    cnt++;
                    if(i-2<0 || nums[i-2] <= nums[i])nums[i-1] = nums[i];                    //modify nums[i-1] of a priority
                    else nums[i] = nums[i-1];                                                //have to modify nums[i]
                }
            }
            return cnt<=1;
        } 
    

  • 1
    S

    Nice explanation´╝ü


  • 0
    A

    Nice Explanation. One optimization though, we can terminate the loop as soon as cnt > 1

    if (cnt > 1) return false;


  • 3
    J

    @abhijeet15 he included that in the for-loop as "cnt <= 1" already.


  • 1
    V

    Same idea. If number of breaks for a non-decreasing order is more than 1, we are bound to change more than 1 element. So, we stop and return false.

    If break happens at boundaries, we can surely change that 1 element, so it will always be true.

    If we find exact 1 break of sequences, we check with break_index-1 and break_index+1 element and if they happen to be non-decreasing, then we can make exactly one change of nums[break_index] to make the sequence non-decreasing.

    If we cannot, similarly we check with break_index-2 and break_index, and if they are non-decreasing, we can change nums[break_index-1] to make it non-decreasing.

    If nothing is possible, we just check with cnt value and return accordingly.

    public class Solution {
        public boolean checkPossibility(int[] nums) {
            
            int cnt = 0;    
            int len = nums.length;
            int break_index = -1;
            
            for(int i=0;i<len-1 && cnt < 2;++i){           
                if(nums[i] > nums[i+1]){
                    cnt += 1;
                    break_index = i+1;
                }            
            }
            
            if(cnt > 1) return false;     
            if(break_index == len-1 || break_index == 1) return true;
            if(cnt == 1 && nums[break_index-1] <= nums[break_index+1]) return true;
            if(cnt == 1 && nums[break_index-2] <= nums[break_index]) return true;
            
            return cnt == 0;
        }
    }
    

  • 1
    B

    @vivek_23 Thank you for your answer. I found it easier to understand than the other ones.

    I had one question though - why do you think that we need to check both (break_index-1 and break_index+1) and (break_index-2 and break_index)? Won't the second case (break_index-2 and break_index) be accounted for, at previous i (due to the (break_index-1 and break_index+1) checks)?

    To be precise, why do we have to check elements at i-1 and i+1 as well as at i-2 and i? Wouldn't those at i-2 and i be checked in the previous iteration (i-1)?


  • 1
    V

    @BatCoder

    Glad to hear that my code was readable to you :)
    Those 2 checks are required because we need to decide which index to change, to join the 2 non decreasing sequences and if neither of them fits, we return false.

    For example, let's take [2,3,3,3,3,2,4]
    Now, the break_index here is 5. So, the 2 sequences are [2,3,3,3,3] and [2,4].
    To join them, the check nums[break_index-1] <= nums[break_index+1], satisfies the non decreasing property and we can change nums[break_index] to 3 for joining.

    Let's take another example - [1,3,5,3,4]
    break_index is 3. Here, nums[break_index-2] <= nums[break_index] fits correctly whereas the other case doesn't which would have forced us to make 2 changes. But, here its quite possible to make a single change, i.e., to make nums[break_index-1] to 3 for joining.

    Last case which fits neither of the 2 checks- [3,4,2,3], so we return false.

    I hope its clear to you now.


  • 0

    Sharing my easy O(N) solution, without modifying the input. click here for more explanation.

    class Solution {
        public boolean checkPossibility(int[] nums) {
            int count = 0;
            for (int i = 0; i < nums.length - 1; i++)
                if (!(nums[i] <= nums[i + 1])) {
                    if (count > 0)
                        return false;
                    if (i - 1 >= 0 && i + 2 < nums.length && (nums[i] > nums[i + 2] && nums[i + 1] < nums[i - 1]))
                        return false;
                    count++;
                }
            return true;
        }
    }
    

  • 1
    B

    @vivek_23
    Perfectly clear. Thank you, Vivek!


  • 0
    N

    Hi, what if the there could exist more than 2 modification, for example 3, 4 or some predefined value k? Any idea?


  • 0
    S

    Got the same idea.
    Python version:

    class Solution(object):
        def checkPossibility(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            if len(nums) <= 1:
                return True
            violation_count = 0
            for i in range(1, len(nums)):
                if nums[i] < nums[i - 1]:
                    violation_count += 1
                    if violation_count == 2:
                        return False
                    if i - 2 >= 0 and nums[i - 2] > nums[i]: # have to promote nums[i]
                        nums[i] = nums[i - 1]
            return True

  • 0

    Sweet... how can I prove the correctness?


  • 0
    W

    Nice! Thank you!


  • 0
    W

    Here is my Python solution

    class Solution(object):
        def checkPossibility(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            cnt = 0
            for i in range(1, len(nums)):
                if cnt > 1: return False
                # use 1,2,3 to denote i-2 i-1 i, 1 largest
                if nums[i-1] > nums[i]:
                    cnt += 1
                    if i < 2 or nums[i-2] <= nums[i]:
                        # from 3 1 2 to 3 2 2
                        nums[i-1] = nums[i]
                    else:
                        # from 2 1 3 to 2 1 1
                        nums[i] = nums[i-1]
                
            return cnt <= 1
    

Log in to reply
 

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