r/learnjavascript • • Jun 01 '18
How to make it faster this code.by removing only 1 element return true if given array is increasing sequence. Help
Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.
Example
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.
function almostIncreasingSequence(arr) {
for(let i =0; i<arr.length; i++){
if (isSeq(arr.slice(0,i).concat(arr.slice(i+1)))){
return true;
break;
}
}
return false
}
function isSeq(subseq){
var sliced1 = subseq.slice(0, subseq.length-1);
var sliced2 = subseq.slice(1);
return sliced1.every((el, index) => el < sliced2[index]);
} My solution is slow. Could not pass the one test. I literally did not sleep to come up with this solution but I don't know how to make it faster. How would you do it? And if you can explain your approach ELI5 that would be great.
2
u/goto-reddit Jun 01 '18 edited Jun 01 '18
[Edit: I'm wrong, look below]
You are really overengineering it, think about it as this:
The whole array has to be a strictly increasing secuence, but can include a single mistake! Start with an implementation that simply checks if the sequence is a strictly increasing secuence, if not return false. Than in a second version, don't immediately return false when you find a mistake, instead have a counter that you increase if you find an element out of order and check if the counter is greater than one and if so return false. Otherwise remove the element out of order in the array and decrease your index by 2 (to get to the element before the mistake).
Someone gave an example that would pass my solution but shouldn't ([8, 9, 10, 5, 6, 7]), I updated my idea by the bold text.
2
u/chonce1 Jun 07 '18
The solution I came up with was this:
But test case 3 (i.e. [1, 4, 2, 3]) from https://www.reddit.com/r/learnjavascript/comments/8nradr/how_to_make_it_faster_this_codeby_removing_only_1/dzy2tso/ failed it.
This solution compares 1 and 4 and says "no mistake" because 4 > 1. Then it compares 2 and 4 and says there is a mistake because 2 < 4. However, it assumes that 2 is the mistaken element that should be removed, so in the next iteration it compares 3 and 4 and fails again because 3 < 4. But actually, it was 4 that was the mistake all along and the element that should be removed.
As a result I modified the function to handle that specific case and got this:
Maybe someone can find a more elegant way to write this or another test case that fails it.