[C++] [Java] Clean Code - 6 liner Without Modifying Input


  • 4

    The strategy is to lower a[i-1] to match a[i] if possible - (a[i-2] not exist or no smaller than a[i]);
    otherwise rise a[i] to match a[i-1].

    2 Examples:
     0  ...  i ...
     1 1 2 4[2]5 6  - in this case we can just raise a[i] to 4;
             4
     1 1 2[4]2 3 4  - in this case lower a[i-1] is better;
           2
    

    Java - Modifying Input

    class Solution {
        public boolean checkPossibility(int[] a) {
            int modified = 0;
            for (int i = 1; i < a.length; i++) {
                if (a[i] < a[i - 1]) {
                    if (modified++ > 0) return false;
                    if (i - 2 < 0 || a[i - 2] <= a[i]) a[i - 1] = a[i]; // lower a[i - 1]
                    else a[i] = a[i - 1]; // rise a[i]
                }
            }
            return true;
        }
    }
    

    We can also do it without modifying the input by using a variable prev to hold the a[i-1]; if we have to lower a[i] to match a[i-1] instead of raising a[i-1], simply skip updating prev;
    Java - Without Modifying Input

    class Solution {
        public boolean checkPossibility(int[] a) {
            int modified = 0;
            for (int i = 1, prev = a[0]; i < a.length; i++) {
                if (a[i] < prev) {
                    if (modified++ > 0) return false;
                    if (i - 2 >= 0 && a[i - 2] > a[i]) continue;
                }
                prev = a[i];
            }
            return true;
        }
    }
    

    Or

    class Solution {
        public boolean checkPossibility(int[] a) {
            int modified = 0;
            for (int i = 1, prev = a[0]; i < a.length; i++) {
                if (a[i] < prev && modified++ > 0) return false;
                if (a[i] < prev && i - 2 >= 0 && a[i - 2] > a[i]) continue;
                prev = a[i];
            }
            return true;
        }
    }
    

    C++ - Modifying Input

    class Solution {
    public:
        bool checkPossibility(vector<int>& a) {
            bool modified = false;
            for (int i = 1; i < a.size(); i++) {
                if (a[i] < a[i - 1]) {
                    if (modified++) return false;
                    (i - 2 < 0 || a[i - 2] <= a[i]) ? a[i - 1] = a[i] : a[i] = a[i - 1];
                }
            }
            return true;
        }
    };
    

    C++ - Without Modifying Input

    class Solution {
    public:
        bool checkPossibility(vector<int>& a) {
            bool modified = false;
            for (int i = 1, prev = a[0]; i < a.size(); i++) {
                if (a[i] < prev && modified++) return false;
                if (a[i] < prev && i - 2 >= 0 && a[i - 2] > a[i]) continue;
                prev = a[i];
            }
            return true;
        }
    };
    

  • 1

    C++ pretty similar approach !

    class Solution {
    public:
        bool checkPossibility(vector<int>& nums) {
            int limit = nums[0];
            int count = 0;
            for (int i=1;i<nums.size();i++){
                if (nums[i]<limit){
                    if (i<2 || nums[i-2]<=nums[i]){
                        limit = nums[i];
                    }
                    if (++count==2) return false;
                }else
                    limit = nums[i];
            }
            return true;
        }
    };
    

  • 0
    G

    @messi14 Preety Similar or same approach


  • 0
    J

    C++ - Without Modifying Input.
    When you find nums[i] > nums[i + 1], there are two scenarios it is fixable: for example, in 425, because 4 <= 5, you can replace 2 by 4 or 5
    in 354, because 3 <= 4, you can replace 5 by 3 or 4...

    bool checkPossibility(vector<int>& nums) {
            int cnt = 0, n = nums.size();
            if (n < 3) return true;
            for (int i = 0; i < n - 1; i++) {
                if (nums[i] > nums[i + 1]) {
                    if (++cnt > 1) return false;
                    int prev = i > 0 ? nums[i - 1] : INT_MIN, nxt = i + 2 < n ? nums[i + 2] : INT_MAX;
                    if (prev > nums[i + 1] && nums[i] > nxt) return false;
                }
            }
            return true;
        }
    

  • 0
    O

    @alexander said in [C++] [Java] Clean Code - 6 liner Without Modifying Input:

    class Solution {
    public boolean checkPossibility(int[] a) {
    int modified = 0;
    for (int i = 1, prev = a[0]; i < a.length; i++) {
    if (a[i] < prev) {
    if (modified++ > 0) return false;
    if (i - 2 >= 0 && a[i - 2] > a[i]) continue;
    }
    prev = a[i];
    }
    return true;
    }
    }

    Is this a redundant statement?
    if (i - 2 >= 0 && a[i - 2] > a[i]) continue;

    Please explain with test case.
    Thanks.


Log in to reply
 

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