Non Decreasing Array

In this approach, we are going to compare current element with next element and if they are not in increasing order, i.e. nums[i] <= nums[i+1], then count it as one modification to make it non decreasing array, repeat this steps until end of array and if the number of modification are 1 or less then return true, false otherwise.

But there is one use case, when we detect an element at index i is greater than the element at i+1, then we need to check for i-1th indexed element as well to ensure the non decreasing order and decide which elements need to copied, consider below examples.

Say if the input array is [2, 4, 3], at index 1 the value is greater than the value at index 2, we can either replace 4 with 3 or 3 with 4, but it is safe to replace 4 with 3,resultant array will become [2, 3, 4]. The reason for this is we dont know what values will come after 3, for example say if the array has one more element 3 on the right side, [2, 4, 3, 3], if we replace index 2 with 1, then the resultant array will not be a non decreasing array [2, 4, 4, 3], but if replace index 2 with 1, then the resultant array will be a non decreasing array [2, 3, 3, 3].

Let's another example, say if the input array is [3, 4, 1], at index 1 the value is greater than the value at index 2, in this case if we replace 4 with 1, then the resultant array will become [3, 1, 1] which is a non-decreasing array because the element on the left side is greater than 1, so in this case, we need to replace 1 with 4, and the resultant array will become [3, 4, 4].

Implementation details:

• Initialize a boolean flag modified to track if a array is modified once, set the intial value to be false.
• Next, loop through array elements from index i = 0 to i = n-1 of the input array and if the number at index i is greater than the element at i+1 index, do the following:
  • First, check modified flag, if this is true, that means array is already modified once, so return false, otherwise continue to next step.
  • If the next element to current element, that is i+1th element is greater than previous element i-1th element, then copy i+1th element to i, by doing so, these 3 positions will satisfy the condition nums[i-1] <= nums[i] <= nums[i+1].
  • Otherwise, copy copy ith indxed element to i+1 index to satisfy the condition satisfy the condition nums[i-1] <= nums[i] <= nums[i+1].
  • If the array is modified once, set the modified flag to true.

public class NonDecreasingArray {

    static boolean checkPossibility(int[] nums) {
        boolean modified = false;

        for(int i=0; i<nums.length-1; i++) {
            if (nums[i] > nums[i + 1]) {

                if (modified) {
                    return false;
                }

                if (i == 0 || nums[i + 1] >= nums[i - 1]) { // i==0 if there are only two elements in array
                    nums[i] = nums[i + 1];
                } else {
                    nums[i + 1] = nums[i];
                }
                modified = true;

            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(checkPossibility(new int[]{4,2,3}));
        System.out.println(checkPossibility(new int[]{-1,4,2,3}));
        System.out.println(checkPossibility(new int[]{4,2,1}));

    }
}

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums array.
Space complexity: O(1), since we are using a boolean flag to track if array is modified once.