Non-decreasing Array | Facebook Interview Question & Solution
This problem was asked by Facebook.
Given an array of integers, write a function to determine whether the array could become non-decreasing by modifying at most 1 element.
For example, given the array [10, 5, 7]
, you should return true
, since we can modify the 10
into a 1
to make the array non-decreasing.
Given the array [10, 5, 1]
, you should return false
, since we can't modify any one element to get a non-decreasing array.
Idea behind the solution
A non-decreasing array requires that, for every i-th
element in the array, it is true that v[i] < v[i+1]
. We are only allowed to change at most 1 number in an array to turn it into a non-decreasing, therefore, at most one v[i] < v[i+1]
can be false
.
If in a given array only one v[i] < v[i+1]
is false
, then v[i-1] < v[i]
is true
, for i > 0
. To be possible to turn the given array into a non-decreasing, we need to change v[i]
to a number such that v[i-1] < v[i] < v[i+1]
is true
. Since the problem states the given array is an array of integers, it is enough to verify if v[i + 1] - v[i-1] > 1
, i.e, if there exists a number between v[i-1]
and v[i+1]
that can be used to assign to v[i]
such that v[i-1] < v[i] < v[i+1]
is true
, for some i > 0
. If i = 0
, we don't need to do the above check since we can pick any integer number lesser than v[i+1]
.
This solutions runs in O(n)
for n
being the length of the array, since we visit each array element only once.
Please check the Solution.java snippet for the solution.
This solution originally posted at: Github by @Murillo2380
Comments
Leave a comment
You are not LoggedIn but you can comment as an anonymous user which requires manual approval. For better experience please Login.