# Non-decreasing Array LeetCode Solution

Difficulty Level Medium

## Problem Statement

Non-decreasing Array LeetCode Solution – given array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[index ] <= nums[index +1] holds for every index (0-based) such that (0 <= index <= n-2).

We need to return true if it could become non-decreasing or else we need to return false.

## Example for Non-decreasing Array LeetCode Solution:

nums = [4, 2, 5]

true

### Input:

nums = [4, 2, 1, 3]

false

## Explanation for Non-decreasing Array LeetCode Solution:

i) For the first test case, we can modify the first element 4 to 1. So that it will be non-decreasing.

ii) For the second test case, no way we can modify just 1 element and make the array non-decreasing.

### Idea:

This problem is like a greedy problem. We can try to change the index only if it does not meet the increasing criteria.

The basic idea is when we encounter some situation where nums[index-1]>nums[index], we need to change the value of nums[index-1] but there might be another case where nums[index-2] > nums[index]. In that case, we need to update the value of nums[index] otherwise to make the array non-decreasing, we will have to update the value of both nums[index-1] and nums[index-2]. We can keep a track of how many times we changed the value to make it non-decreasing. If it’s more than 1 the output will be false or else it will be true.

## Code

### Java Program for Non-decreasing Array

```class Solution {
public boolean checkPossibility(int[] nums) {
int changeCount = 0;
for(int index = 1; index < nums.length && changeCount <=1 ; index++){
if(nums[index-1] > nums[index]){
changeCount++;
if(index-2<0 || nums[index-2] <= nums[index ])
nums[index-1] = nums[index];
else nums[index] = nums[index-1];
}
}
return changeCount<=1;
}
}```

### C++ Program for Non-decreasing Array

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

## Complexity Analysis for Non-decreasing Array LeetCode Solution

### Time Complexity

Here we are just iterating over the array once. So the time complexity is O(n). (n is the size of the array)

### Space Complexity

The space complexity of the above code is O(1) because we are not using any extra space.

Translate »