Non-Decreasing Array

Moderate

0/80

Average time to solve is 35m

161 upvotes

Asked in companies

Problem statement

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

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

Sample Output 1 :

true
false

Explanation to Sample Input 1 :

For Test Case 1 we can have a possible non-decreasing array : 2 4 6
Where only the element at index 0 has been modified.

For Test Case 2 there is no possible way to make the array non-decreasing by modifying at most 1 element.

Sample Input 2 :

2
6
-2 7 -1 0 1 2
5
-10 10 0 10 3

Sample Output 2 :

true
false

Explanation to Sample Input 2 :

For Test Case 1 we can have a possible non-decreasing array : -2 -2 -1 0 1 2
Where only the element at index 1 has been modified

For Test Case 2 there is no possible way to make the array non-decreasing by modifying at most 1 element.

Hint 1

Hint 2

Hint 3

You can try to modify every index one by one and check whether it is possible to make the array non-decreasing.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

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

Time Complexity

O(N ^ 2), where ‘N’ is the length of the array.

For every index, we are modifying it and linearly checking if this modification makes the array non-decreasing. Hence, time complexity will be O(N ^ 2).

Space Complexity

O(1).

As we are using constant extra space.

(100% EXP penalty)

Non-Decreasing Array

Console