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)
Top comments (0)