DEV Community

Cover image for Leetcode 665. Non-decreasing Array
Ruhul Amin πŸ‡§πŸ‡©
Ruhul Amin πŸ‡§πŸ‡©

Posted on

Leetcode 665. Non-decreasing Array

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

  1. 5,9,4
  2. 4,9,5
  3. 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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)