Non-Decreasing Array

Posted: 10 Sep, 2020
Difficulty: Moderate


Try Problem

You have been given an integer array/list 'ARR' of size 'N'. Write a solution to check if it could become non-decreasing by modifying at most 1 element.

We define an array as non-decreasing, if ARR[i] <= ARR[i + 1] holds for every i (0-based) such that (0 <= i <= N - 2).

Input format :
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains an Integer 'N' denoting the size of the array/list.

The second line of each test case contains 'N' space-separated Integers denoting the array/list.
Output format :
For each test case, print a single line containing "true" if it's possible to make 'ARR' non-decreasing array with modifying at most one element or "false" otherwise. 

The output for every test case will be printed in a separate line.
Note :
You do not need to print anything, it has already been taken care of.  Just implement the given function.
Constraints :
1 <= T <= 50
1 <= N <= 10 ^ 4
- 10 ^ 9 <= ARR[i] <= 10 ^ 9

Where 'N' is the size of the given array/list.
And, ARR[i] denotes the i-th element in the array/list 'ARR'.

Time Limit: 1sec
Approach 1

As we are allowed at most one modification, we can try it on every index separately and naively check whether the array becomes non-decreasing by any modification. For this, we can modify the starting index (i.e. 0) to a very less value (say INT_MIN) and the rest of the indexes as the value of the preceding element if present (i.e. ARR[i] = ARR[i - 1]). 

Try Problem