Non-decreasing Array


  • 0

    Click here to see the full article post


  • 0
    D

    I can't believe this is an easy problem.


  • 0
    W

    I think your explanation for approach 3 is a bit over-complicated and hard to understand at first glance.

    You can reduce all the cases you are considering to the following:

    Check if there exists any pair (i, i+1) that is decreasing i.e. (i+1) < i
    If no, return true
    If yes, check two cases:
    set nums[i] = nums[i+1] and check if array is decreasing (assign to boolean, b1)
    (reset original values)
    set nums[i+1] = nums[i] and check if array is decreasing (assign to boolean, b2)
    return b1 || b2

    This covers the edge cases for start and end of array for you.


  • 0
    Y

    I also think my solution is grace.

    class Solution {
    public boolean checkPossibility(int[] nums) {
    boolean used = false; // one opportunity to modify
    Stack<Integer> st = new Stack<>();

        for(int i = 0 ; i < nums.length ; i ++){
            if(!st.empty()){
                if(st.peek() > nums[i]){ // not mono increasing , used the opportunity
                    if(used) return false;
                    used = true;
                    int ele = st.pop();  // need to decide how to eliminate the drop , which element to remove(change).
                    if(!st.empty() && st.peek() > nums[i]){
                        st.push(ele); // don't insert the new element 4 -> 5  , if new element is 2 then don't insert it
                        continue;
                    }
                    else{
                        st.push(nums[i]); // this is for 4 , 7 , 5 case , we should remove 7 and insert 5 since 5 is smaller. and better 
                                          // change next element will follow the rule of increasing.
                    }
                }
                else st.push(nums[i]);// normal case , insert new element 
            }
            else st.push(nums[i]);// insert the first element to stack , each time we will insert an element for sure , and remove at most 1 
        }                         // element , that means the number of element in stack won't decrease , this is the first element in stack
        return true;
    }
    

    }


  • 0
    N

    Simple java solution :
    int count = 0;
    int i = 0;
    if (nums == null) {
    return false;
    }
    while (i < nums.length - 1) {
    if (count > 1) {
    return false;
    }
    if ((nums[i] > nums[i + 1])) {
    if(i+2 < nums.length && nums[i+2] < nums[i]) {
    nums[i] = nums[i+1] - 1;
    } else {
    nums[i + 1] = nums[i];
    }
    i = 0;
    count++;
    } else {
    i++;
    }
    }

            return true;

  • 0
    A

    does anybody have it's C# code?


  • 0
    P

    Easy:

    def checkPos(array):
    return sum(array[i] > array[i + 1] for i in range(len(array) - 1)) <= 1


  • 0
    Y

    JavaScript

    var checkPossibility = function(nums) {
        var count = 0
        for(var i = 0; i < nums.length; i++) {
            for(var j = i + 1; j < nums.length; j++) {
                if(nums[i] > nums[j]){
                    count = count + 1
                    break
                }
            }
        }
        return count <= 1
    };
    

  • 0
    C

    Approach # 3, very well explained with cases


  • 0

    case 3 is a good solution but i would rather use another var to indicate the counting time, and an index to remember the location.


  • 0
    C
    This post is deleted!

Log in to reply
 

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