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


  • 36

    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;
        } 
    

  • 3
    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;


  • 4
    J

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


  • 3
    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

    @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

    @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
    

  • 1
    L

    if we delete the condition i-2<0 the code will also been accepted.


  • 0

    @liyiye I guess you are using C++. When you remove i - 2 <0, you will use nums[-1] if i=1. In C++, it's called undifined behavior. std::vector operator [] won't throw any out of range error, and you might get nums[-1] = 0 actually. If you use std::vector::at instead, it will throw std::out_of_range.

    You can have a test of nums = {2, -2, -1}, there would be different results while removing or not removing i - 2 <0.


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

  • 0
    M

    Great solution. Below is a little explanation for those having trouble understanding.

    The problem requires that every number has to be equal or greater than previous number.
    If we encounter a failing condition where the number is not greater or equal to previous (smaller than previous) we need to make a correction. Correction can be made in either of two ways:

    1. Make the previous number smaller or equal to current number
    2. Make the current number equal to previous number

    We can do (1) as long as the number at position i-2 is equal or lower than the current element. (if i-2 is valid)
    In case 1 below we can do this at (3) (i = 2) as the element 1 (i = 0) fulfills 1 <= 3. We can replace 7 with 3.
    However, this cannot be done in case 2 as 4 <= 3 does not satisfy.

    Correction with technique (1) takes priority as there is no risk in lowering the value but there is a risk associated if the value is increased. (Consider scenario in case 1 if we replace 3 with 7, it will fail to satisfy the condition for the last element)

    We have to make correction with (2) if we cannot achieve it by (1). In which case we increase the value of current element by matching previous element. In case 2, we replace 3 with 7.

    Also we only compare condition with the previous element only because as we move forward we know the previous numbers are already validated .

    Case 1:
         7
         /\    4
        /  \  /
       /    \/
      /      3
     1
     
    Case 2:
              9
             /
       7    /
       /\  /
      /  \/
     /    3
    4
    

Log in to reply
 

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