Non-decreasing Array (Leetcode 665)

Leetcode 665

Difficulty: Medium Link: Day 4 : May Leetcode Challenge

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

Examples

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.

Constraints

  • n == nums.length
  • 1 <= n <= 104
  • -105 <= nums[i] <= 105

Solution

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.

Valid Non decreasing Sequences.

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.

Ways to modify an Element

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.

Code

Swift

class Solution {
func checkPossibility(_ nums: [Int]) -> Bool {
var count = 0
var nums = nums
for i in 1..<nums.count {
if nums[i] < nums[i 1] {
if i == 1 || nums[i 2] <= nums[i] {
nums[i 1] = nums[i]
count += 1
}
else{
nums[i] = nums[i 1]
count += 1
}
}
}
return count <= 1
}
}

Python

class Solution:
def checkPossibility(self, N: List[int]) -> bool:
err = 0
for i in range(1, len(N)):
if N[i] < N[i1]:
if err or (i > 1 and i < len(N) 1 and N[i2] > N[i] and N[i+1] < N[i1]):
return False
err = 1
return True
view raw checkpossibility.py hosted with ❤ by GitHub

Java

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

Complexity Analysis

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)

Leave a Reply

Your email address will not be published. Required fields are marked *