MayLeetCoding Challenge 2021 — Day 4: Non-decreasing Array

Today is May the 4th. Happy Star Wars Day everyone.

Let’s solve some Leetcode problems today. Today we will solve the 4th problem of the May LeetCoding Challenge 2021.

Problem Statement

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

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.

Solution

We are going to solve this problem greedily. We can modify at array at max 1 time so that it becomes a non-decreasing array.

To achieve that, we have to take care of few things.

• When modifying the number at index i-1 , we need to consider elements at i-2 and i -th index.

• Need to make sure that the array satisfies the conditions even after modifications are made.

Correction can be made in either of two ways:

1. Make the previous number smaller or equal to the current number

2. Make the current number equal to the previous number

We can do the first as long as the number at position i-2is equal or lower than the current element(index i),if i-2is valid. If we can’t then go for the second condition. We give priority to the first case.

Check the code below.

Time complexity:O(n)

Space complexity:O(1)

Check the whole repository for more leetcode solutions.
sksaikia/LeetCode