We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that
(0 <= i <= n - 2).
Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
Input: nums = [4,2,1]
Output: false
Explanation: You cannot get a non-decreasing array by modifying at most one element.
Constraints:
- n == nums.length
- 1 <= n <= 104
- -105 <= nums[i] <= 105
Contents
- Solution 1 - Compare previous and next elements and track modified count
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.
Example 1:
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].
Example 2:
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.
Above implementations source code can be found at
GitHub link for Java code