Non-decreasing Array


2 min read

Problem Statement

Given an 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[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Example 1:

Input: nums = [4,2,3]

Output: true

Explanation: You could modify the first 4 to 1 to get a non-decreasing array.


We are only allowed to modify once.

While modifying we had two options, either to change nums[i-1] or nums[i].

But for that, we need to check the value of nums [i-2] value also provided i-2>=0

1 5 4 4, Let i =2, Here nums[i] > nums[i-2], and since nums[i-1] is also greater than nums[i-2], we can simply modify at nums [i-1]= nums[i];

3 5 2, let i=2, Here nums[i] < nums[i-2], and since nums[i-1] must be already greater than nums[i-2], we can use the value of nums[i] = nums[i-1]

And if the changed value increases to any number greater than 1, it means we need to alter more than 1 element which is not allowed. Hence, We return false at that moment.

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

Time Complexity:- O(N)

Space Complexity:- O(1)