Non-decreasing Array — Leetcode 665

Original problem link: https://leetcode.com/problems/non-decreasing-array/description/

In this problem, we’re asked whether a given array can become non-decreasing with the modification of at most one element in the array.

This is one of those problems where one really needs to think all the cases through. Intuitively, we can check each triple of numbers like a sliding window of size 3, and flip the numbers in the array based on what the minimum combination to make it a valid nondecreasing array would be.

I know this is not the shortest solution but it does give lots of details on the necessary math comparisons :)

The runtime is between 1–5 ms most of the time.

class Solution {
    public boolean checkPossibility(int[] nums) {
        if (nums.length < 3) {
            return true;
        }

        int flipped = 0;
        for (int i = 1; i < nums.length - 1; i++) {
            int diff1 = nums[i] - nums[i - 1];
            int diff2 = nums[i + 1] - nums[i];
            if (diff1 < 0 && diff2 < 0) {
                // 2 consecutive decreasing numbers, which immediately means we cannot only change one to make it nondecreasing
                return false;
            } else if (diff1 >= 0 && diff2 < 0) {
                // change one of the second pair, based on comparison between end and beginning of triplet
                if (nums[i + 1] >= nums[i - 1]) {
                    nums[i] = nums[i + 1];
                } else {
                    nums[i + 1] = nums[i];
                }
                flipped++;
            } else if (diff1 < 0 && diff2 >= 0) {
                // change one of the first pair, based on comparison between end and beginning of triplet
                if (nums[i + 1] >= nums[i - 1]) {
                    nums[i] = nums[i - 1];
                } else {
                    nums[i - 1] = nums[i];
                }
                flipped++;
            }

            if (flipped >= 2) {
                // we've already changed too many
                return false;
            }
        }

        return true;
    }
}