Last Updated: 10 Sep, 2020
Non-Decreasing Array
Moderate
Asked in companies
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
Approaches
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]).
The idea is to trim the array ‘ARR’ on both sides and check for the part in the ARRay where the modification is actually required. Suppose if ARR[0] <= ARR[1] <= ARR[2], then we can remove ARR[0] (don’t consider it for modification) from the ‘ARR’. Similarly, we can trim some parts from the back of the ‘ARR’ also.
Here is the complete algorithm-
- Initialize ‘START’ to 0 and ‘END’ to N - 1. These pointers will help us in trimming the array from both sides.
- Increment the ‘START’ pointer till ARR[START] <= ARR[START + 1] <= ARR[START + 2].
- Decrement the ‘END’ pointer till ARR[END - 2] <= ARR[END - 1] <= ARR[END].
- Now, if ‘END’ - ‘START’ + 1 <= 2, we don’t need to modify any element. So, return true.
- Now, Else if ‘END’ - ‘START’ + 1 >= 5, it’s impossible to make the ‘ARR’ non-decreasing. So return false.
- Else, the array can only be checked for modification in the subarray starting from index ‘START’ to ‘END’. For this, we can use the brute force method from approach 1.
We need to find all the indices ‘IDX’ which are not in non-decreasing order or we can say all the indices which satisfy ARR[IDX] > ARR[IDX + 1].
Now we can build our logic based on these indices:
- If there are more than 2 then the answer is false as more than one element of the ‘ARR’ must be changed to make the ‘ARR’ non-decreasing.
- If there are zero indices, then the answer is True as the ‘ARR’ is already non-decreasing.
- Now we are only left with cases where there is only 1 index which is not in order:
- If IDX == 0 then we can make the ‘ARR’ good by setting ARR[IDX] = ARR[IDX + 1]
- If IDX == N - 1 (Where ‘N’ is the size of the ‘ARR’) then we can make the ‘ARR’ good by setting ARR[IDX] = ARR[IDX - 1]
- Now we are sure for leftover cases ARR[IDX-1] , ARR[IDX], ARR[IDX + 1], ARR[IDX + 2] exist. It is possible to make the ‘ARR’ good:
- If we could change ARR[IDX] to be between ARR[IDX - 1] and ARR[IDX + 1]
- If we could change ARR[IDX + 1] to be between ARR[IDX] and ARR[IDX + 2]
- For the rest of the cases, it’s impossible to make the ‘ARR’ non-decreasing by modifying at most 1 element.
Similar problems