This post is completed by 3 users

Add to List 
Convert to Nondecreasing Array with one change
Given an array of numbers, you need to find out whether an array can be converted to a nondecreasing array where you are allowed to modify the maximum one element in the array.
Nondecreasing array: Array is called a nondecreasing array when you traverse the array from left to right, each element on the left is less than equal to the element on the right. So for any element at index i, input[i1]<=input[i]<=input[i+1].
Example:
Input[] = [4, 5, 1, 7] Output: true Change 1 to 6 or 5 or 7 Input[] = [10, 5, 2] Output: false Input: [1, 2, 1, 5] Output: true Change 2 to 1. Input: [1, 1, 1, 1] Output: true No Change required
Solution:
We are allowed to modify one element and we need to check both the possibilities of increasing or decreasing a number. For example, [4, 5, 1, 7], we will increase the element 1 to 6 whereas, in example [1, 5, 4], we will decrease the element 5 to 2 or 3.
So Iterate the array from right to left and count how many elements we need to decrease if the element on the left is greater than the element at the right. Then iterate the array from left to right and check how many elements we need to increase if the element on the right is less than the element on the left.
An important point to remember is  we will increase to decrease the element so that it will just pass the nondecrement condition so increase to decrease the element to make it equal to its neighbor element. Example  [1, 2, 1, 5], decrement the element 2 to 1 so make it equal otherwise we cannot make the array nondecreasing.
Time Complexity: O(N)
Output:
true false true true
Also Read: