Non-Decreasing Array
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]

Question

Non-Decreasing Array

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

Accepted Answer

The solution checks if an integer array can become non-decreasing by modifying at most one element.

Iterate through the array and check if there are more than one decreasing pairs of elements.
If there are more than one decreasing pairs, return false.
If there is only one decreasing pair, check if modifying one of the elements can make the array non-decreasing.
If modifying the element at index i-1 or i can make the array non-decreasing, return true.
Otherwise, return false.

Accepted Answer

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

Space Complexity: O(1)Explanation:

O(1).

As we are using constant extra space.

Time Complexity: O(n^2)Explanation:

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

Accepted Answer

Prune the range of Brute Force

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.

Space Complexity: O(1)Explanation:

O(1).

As we are using constant extra space.

Time Complexity: O(n)Explanation:

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

As we iterate through every element only once by either of the two pointers it will cost O(N). Now we are using the brute force check on at max 4 index so it will cost O(4 * N). So Overall Time Complexity is linear.

Accepted Answer

Finding Indices which are not in non-decreasing order

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.

Space Complexity: O(1)Explanation:

O(1).

As we are using constant extra space.

Time Complexity: O(n)Explanation:

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

As we are just iterating from left to right once in the array for checking the condition and doing some constant comparisons after that. Therefore, overall time complexity will be O(N).

Accepted Answer

good decision

Accepted Answer

thats called time waisting please call me & joined the date

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 :

Output format :

Note :

Constraints :

Top Josh Technology Group Front end Developer interview questions & answers

Popular interview questions of Front end Developer

Top HR questions asked in Josh Technology Group Front end Developer