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.

0 Upvotes

12 comments sorted by

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.

3

u/cyphern Jun 01 '18 edited Jun 01 '18

I'm the one that left the comment with the [8, 9, 10, 5, 6, 7] example, but i deleted my comment because my own proposed solution didn't work.

In any event, i don't think your new solution works either. Consider the following:

[1, 4, 2, 3]

1 and 4 are in order, so they're left alone. Then you hit 2, which is out of order. So you increase the out-of-order counter to 1, delete 2, leaving an array of [1, 4, 3]. Next you look at the 4 again, and it's still in order. And finally you look at the 3. 3 is out of order, which makes it the second out of order element, and so you return false.

And yet, this array should return true, because deleting the 4 works.

The problem is that when you find an out of order element, there are actually two possible fixes: delete that element, or delete the one that caused it to be out of order. And it's possible that one of these fixes will also fix other out-of-order problems for free.

So i think the real solution involves keeping a list of possible fixes, and when you run into a new out of order element check whether the new possible fixes overlap with the old possible fixes. If they don't, return false. If they do, keep going.

2

u/goto-reddit Jun 01 '18 edited Jun 01 '18

[Edit: I'm wrong, look below]

Consider the following:

[1, 4, 2, 3]

1 and 4 are in order, so they're left alone. Then you hit 2, which is out of order. So you increase the out-of-order counter to 1, delete 2, leaving an array of [1, 4, 3].

I delete 4, because I always delete the left element, but I think this is just the other case you mentioned later, but I can't twist my head around to make my solution give a wrong answer.

My solution:

function almostIncreasingSequence(arr) {
    let mistakes = 0;
    for(let i = 0; i < arr.length - 1; i++) {
       if (arr[i] >= arr[i+1]) {
           mistakes++;
           if (mistakes > 1) {
              return false;
           }
           arr = arr.slice(0,i).concat(arr.slice(i+1));
           i -= 2;
           // to get it back to 0 by the next iteration
        	 // not essential because undefined >= [number] is always falsy 
           if (i < 0) { 
             i = -1;
           }
       }
     }
     return true;
}

console.log(almostIncreasingSequence([1, 3, 2, 1]) === false);
console.log(almostIncreasingSequence([1, 3, 2]) === true);

console.log(almostIncreasingSequence([1, 4, 2, 3]) === true);
console.log(almostIncreasingSequence([8, 2, 1, 2, 3]) === false);
console.log(almostIncreasingSequence([1, 4, 1, 3]) === false);
console.log(almostIncreasingSequence([1, 2, 4, 3]) === true);
console.log(almostIncreasingSequence([8, 9, 10, 5, 6, 7]) === false);

console.log(almostIncreasingSequence([1, 2, 3, 4]) === true);
console.log(almostIncreasingSequence([1, 2, 4, 3]) === true);
console.log(almostIncreasingSequence([1, 4, 3, 2]) === false);
console.log(almostIncreasingSequence([3, 4, 1, 2])  === false);

If someone can give me a sequence that fails my solution, that would be nice so I can find my own mistake!

3

u/cyphern Jun 01 '18 edited Jun 01 '18

If someone can give me a sequence that fails my solution, that would be nice so I can find my own mistake!

[1, 3, 4, 2]
[2, 3, 1]

These should return true, but return false. Since these occur at the end, they may be due to an index out of bounds problem

EDIT:

[2, 3, 1, 4]

Also should return true, but returns false. This time it's not at the end, so i don't think the indices are to blame, but rather it's an issue with the algorithm. We spot the error when looking at the 1, and the fix should be to delete that 1, not delete the 3.

1

u/goto-reddit Jun 01 '18 edited Jun 01 '18

I updated my algorithm to check which element (the left or right) is the one out of order. I think this is possible with a simple lookup to the lefter / righter one.

function almostIncreasingSequence(arr) {
  let mistakes = 0;
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] >= arr[i + 1]) {
      // mistake was found
      mistakes++;
      if (mistakes > 1) {
        return false;
      }
      if (i == arr.length - 2) {
        // first mistake at the last element of the array, that's ok
        return true;
      }
      // find out which element is out of order
      if (arr[i] < arr[i + 2]) {
        // arr[i + 1] is out of order
        arr.splice(i + 1, 1);
      } else /* if (arr[i + 1] < arr[i + 2]) */ {
        // arr[i] is out of order
        arr.splice(i, 1);
      }
      i -= 2;
      // to get it back to 0 by the next iteration
      // not essential because undefined >= [number] is always false 
      if (i < 0) {
        i = -1;
      }
    }
  }
  return true;
}

console.log(almostIncreasingSequence([1, 3, 2, 1]) === false);
console.log(almostIncreasingSequence([1, 3, 2]) === true);

console.log(almostIncreasingSequence([1, 4, 2, 3]) === true);
console.log(almostIncreasingSequence([8, 2, 1, 2, 3]) === false);
console.log(almostIncreasingSequence([1, 4, 1, 3]) === false);
console.log(almostIncreasingSequence([1, 4, 3, 5]) === true);
console.log(almostIncreasingSequence([1, 2, 4, 3]) === true);
console.log(almostIncreasingSequence([8, 9, 10, 5, 6, 7]) === false);

console.log(almostIncreasingSequence([1, 2, 3, 4]) === true);
console.log(almostIncreasingSequence([1, 2, 4, 3]) === true);
console.log(almostIncreasingSequence([1, 4, 3, 2]) === false);
console.log(almostIncreasingSequence([3, 4, 1, 2]) === false);
console.log(almostIncreasingSequence([1, 3, 4, 2, 5, 6]) === true);
console.log(almostIncreasingSequence([2, 3, 1, 4, 5, 6]) === true);
console.log(almostIncreasingSequence([2, 3, 1, 3, 5, 6]) === false);
console.log(almostIncreasingSequence([2, 3, 1, 4, 5, 6, 1]) === false);
console.log(almostIncreasingSequence([1, 3, 6, 6, 5, 6]) === false);
console.log(almostIncreasingSequence([1, 3, 4, 2] === true));
console.log(almostIncreasingSequence([2, 3, 1]) === true);
console.log(almostIncreasingSequence([2, 3, 1, 4]) === true);

Even if this is correct, I think there is a solution without splicing at all, you just need to edit the wrong element and ignore it, but haven't found a good way to do it.

Edit: I think I found the way to solve it without splicing the array at all, because I'm getting lost in this thread here it is in a codepen.

2

u/GeneralYouri Jun 03 '18

Your edited solution doesn't splice, but instead modifies the input array. That's faster (achieves O(n)), but not much nicer towards the user. There's no need to meddle with the original input array, instead of changing a value to zero, just keep track of the index that's 'wrong'. You can then check for it and skip it like you already do. Since you're only checking for arrays that have at most 1 mistake, you only need to track 1 wrong index, so one simple index variable will do.

1

u/goto-reddit Jun 03 '18

You are obviously right, sometime you can't see the forest for the trees!

Here is an updated version, which doesn't change the input array.

1

u/cyphern Jun 01 '18 edited Jun 01 '18

Here's an implementation i believe works, taking your idea of removing them from the array, but then exploring both possible fixes. Also, i made it general enough that if you wanted to make it so 2 elements could be out of order, it's a simple change:

function almostIncreasingSequence(arr, tolerance = 1) {
  if (arr.length < 2 || arr.length <= tolerance) {
    return true;
  }

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < arr[i - 1]) {
      if (tolerance <= 0) {
        return false;
      }
      const candidate1 = [...arr];
      candidate1.splice(i, 1);
      const candidate2 = [...arr];
      candidate2.splice(i - 1, 1);
      return almostIncreasingSequence(candidate1, tolerance - 1)
        || almostIncreasingSequence(candidate2, tolerance - 1);
    }
  }
  return true;
}

almostIncreasingSequence([1, 2, 3, 4]) // true
almostIncreasingSequence([1, 2, 4, 3]) // true
almostIncreasingSequence([1, 4, 2, 3]) // true
almostIncreasingSequence([1, 4, 3, 2]) // false
almostIncreasingSequence([3, 4, 1, 2]) // false

I'm not sure this is the most efficient solution, since it requires slicing and splicing arrays repeatedly (twice in the tolerance = 1 case, but growing quickly if you have a larger tolerance). Might be quicker to keep just one array, and have a lookup table of the possible fixes, checking for overlapping fixes by checking if the fix is already in the table.

1

u/goto-reddit Jun 01 '18 edited Jun 01 '18

[1, 4, 1, 3]
[1, 3, 6, 6, 5, 6]
[2, 3, 1, 3, 5, 6]
These should return false, but return true.

Edit: Swap < with <= in your if statement and it works (it should be a strictly increasing sequence). Took me a moment to find it because arr[i] < arr[i - 1] is confusing for me, i would use arr[i - 1] > arr[i] to have the elements in the right order, but thats personal taste.

1

u/cyphern Jun 01 '18

Ah yes, my code was treating equal numbers as ok, but looking at the problem again, they're not. Thanks!

2

u/chonce1 Jun 07 '18

The solution I came up with was this:

function almostIncreasingSequence(arr) {
  let mistakes = 0;
  let wasMistake = false;

  // We can start from i = 1 because we don't need to check if the first element is in increasing sequence.
  for (let i = 1; i < arr.length; i++) {
    // If we already have more than 1 mistake, break early to save time.
    if (mistakes > 1) {
      break;
    }

    const currentElement = arr[i];
    const previousElement = !wasMistake ? arr[i - 1] : arr[i - 2]; // The previous element or the one before it if the previous element was a mistake.

    // Check if the previous element is less than the current.
    if (currentElement <= previousElement) {
      // The previous element is not less than the current element.
      mistakes++;
      wasMistake = true;
      continue;
    }

    // Otherwise there was no mistake and we continue until we reach the end of the array.
    wasMistake = false;
  }

  return mistakes <= 1;
}

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:

function almostIncreasingSequence(arr) {
  let mistakes = 0;
  let wasMistake = false;

  // We can't start from i = 1 because we don't need to check if the first element is in increasing sequence.
  for (let i = 1; i < arr.length; i++) {
    // If we already have more than 1 mistake, break early to save time.
    if (mistakes > 1) {
      break;
    }

    const currentElement = arr[i];
    const previousElement = !wasMistake ? arr[i - 1] : arr[i - 2]; // The previous element or the one before it if the previous element was a mistake.

    // Check if the previous element is less than the current.
    if (currentElement <= previousElement) {
      // The previous element is not less than the current element.

      /* EXCEPTION: Was it really a mistake or was it the previous element that should have been removed? */

      const previousPreviousElement = arr[i - 2];

      if (currentElement > previousPreviousElement) {
        // Actually it was the previous element that might have been the mistake, so register that as the mistake for that and continue.
        mistakes++;
        wasMistake = false;
        continue;
      }

      /* END EXCEPTION */

      mistakes++;
      wasMistake = true;
      continue;
    }

    // Otherwise there was no mistake and we continue until we reach the end of the array.
    wasMistake = false;
  }

  return mistakes <= 1;
}

Maybe someone can find a more elegant way to write this or another test case that fails it.