Non-decreasing Array LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Bloomberg eBay Facebook Google Microsoft YahooViews 3630

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:

Test Case 1:

Input:

nums = [4, 2, 5]

Output:

true

Test Case 2:

Input:

nums = [4, 2, 1, 3]

Output:

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.

Approach

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.

Reference: https://en.wikipedia.org/wiki/Greedy_algorithm

 

Translate »