Leetcode 665. Non-decreasing Array

Ruhul Amin 🇧🇩 — Wed, 05 May 2021 15:32:59 +0000

At first glance, this problem seems to be easy but I was getting the wrong answer again and again. then I figure out the solution to this problem.
you can modification only one element to make an array non decreasing order.
let's consider three test case

5,9,4
4,9,5
5,4

for test case 1: 5,9 is increasing order but 4 is in downfall so we will compare this index(let's consider it i) with i-2. if i-2 is greater than I then we will modify I with i-1 so the final array will be 5,9,9 that in non-decreasing order.

for test case 2: 4,9 is increasing order but 5 is in downfall so we will compare this index(let's consider it i) with i-2. if i-2 is less than I then we will modify i-1 with I so the final array will be 4,5,5, which is non decreasing order.

for test case 3: when elements are less than three then if the value of the ith index is less than the value i-1th index then we can modify the i-1th index with I so the array will be 4, 4 that is non decreasing order.
here is my c++ code

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

time complexity: O(n)
space complexity: O(1)

DEV Community: Ruhul Amin 🇧🇩

Leetcode 665. Non-decreasing Array