Difficulty: Medium Link: Day 4 : May Leetcode Challenge
Given an array
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).
Input: nums = [4,2,3] Output: true Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
Input: nums = [4,2,1] Output: false Explanation: You can't get a non-decreasing array by modify at most one element.
n == nums.length
1 <= n <= 104
-105 <= nums[i] <= 105
The problem might seem a bit easy at first. You might intuitively think to count the number of elements which are violating the non-decreasing property (nums[i] >= nums[i – 1]) and if that count is greater than one, then its not possible to form a non-decreasing sequence. Well thats one part of the problem and as you try more examples, you would realise that problem has some tricky edge cases. Let us see what a valid non-decreasing array mean.
The Problem becomes tricky when you realise that you can modify one element which in turn can impact its relationship with the other elements. Whenever we find a pair which is decreasing in nature (Array[i] < Array[i – 1]), we can modify it in two ways to get a valid sequence. Choice 1: By decreasing the larger value and Choice 2: by increasing the smaller value. Carefully observe the diagram below as we are going to use the same idea on the solution.
As you can see in the example, to convert [2,1] into a non-decreasing sequence, we had two choices, Case A decreased the larger value to level up with the lower one. In Case B, We increased the lower value to the level of larger one. Now it would depend on the the previous value which condition should be take! How? Look at the example.
As we can see, while considering three elements (Num[i], Num[i – 1], Num[i – 2]), Choice A would not give the valid result but Choice B would be a wise one. Hence, we would also need to consider the (i – 2) th element and if it is less than or equal to the ith element, this means that we can i decrease the i – 1 th element (Choice A). Else there is no other way except increasing the ith element. We will also consider a special case for i = 1, since there is no (i – 2)th element and therefore, we will try to decrease the larger value. Why? Because we do not know which values are to come next hence it is optimal to convert into non-decreasing sequence by reducing the higher value.
We are iterating the array once, so N order operations are performed. Also, since we are only using count variable thus it is a constant space solution.
Time = O(N)
Space = O(1)