665. Non-decreasing Array

Description

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).

Constraints

• n == nums.length

• 1 <= n <= 104

• -105 <= nums[i] <= 105

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: nums = [4, 2, 3]

Output: true

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

Example 2

Input: nums = [4, 2, 1]

Output: false

Explanation: You can't get a non-decreasing array by modify at most one element.

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public boolean checkPossibility(int[] nums) {
        if(nums == null || nums.length <= 2) {
            return true;
        }
        int count = 0;
        for(int i = 1; i < nums.length; i++) {
            if(nums[i-1] > nums[i]) {
                count++;
                if(i-2 < 0 || nums[i-2] <= nums[i]) {
                    nums[i-1] = nums[i];
                } else {
                    nums[i] = nums[i-1];
                }
            }
        }
        return count <= 1;
    }
}

Follow up