This was part of my interview questions.
Given a sequence of integers as an array, I have to determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.
For instance,
For
sequence = [1, 3, 2, 1]
, the output should be
almostIncreasingSequence(sequence) = false
There is no one element in this array that can be removed in order to get a >strictly increasing sequence.
For sequence =
[1, 3, 2]
the output should be
almostIncreasingSequence(sequence) = true
We can remove 3 from the array to get the strictly increasing sequence
[1, 2]
. Alternately, we can remove 2 to get the strictly increasing sequence[1, 3]
.The function must return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return
false
.
The conceptual algorithm that the interviewer wanted was below with Java:
boolean almostIncreasingSequence(int[] sequence) {
int seq1 = 0;
int seq2 = 0;
for(int i = 0; i < sequence.length - 1; i++){
if(sequence[i] >= sequence[i + 1]) seq1++;
}
for(int k = 0; k < sequence.length - 2; k++){
if(sequence[k] >= sequence[k + 2]) seq2++;
}
return !(seq1 + seq2 > 2);
}
but I didn't get the part comparing sequence[i]
with sequence[i+1]
andsequence[i+2]
to increment the counter which are seq1
and seq2
. How does this cover all the cases?
i
for whicha[i] > a[i+1]
and for that indexa[i-1] < a[i+1]
(ori == 0
). That's not what the algorithm does, though. $\endgroup$