# 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**:

- Make the previous number smaller or equal to the current number
- Make the current number equal to the previous number

We can do the first as long as the number at position `i-2`

is equal or lower than the current element(index `i`

),if `i-2`

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