Discussion on: Daily Challenge #273 - Remove Duplicates

[JP Antunes]

Simple JS O(n) solution (I think... 2n?) that will remove the left-most duplicates from a list of integers and return the result in the right order.

const solve  = arr => {
    let seen = [];
    for (let i = arr.length - 1;  i > 0; i--) {
        seen.includes(arr[i]) ? _ : seen.unshift(arr[i])
    }
    return seen;
}

[Vinay Pai]

This is not O(n) because you're iterating over "seen" at every iteration of your for loop, so it's O(n^2) except in the degenerate case where all the elements are duplicates. Also, it isn't specified but unshift itself is also most likely an O(n) operation in most implementations.

[JP Antunes]

I had my doubts, but it seems the JS implementation uses a linear search algorithm.

FWIW, I also had to check if Sets keep insertion ordering since in principle they shouldn't... but in JS they do!

[Vinay Pai]

Good to know, I didn't know that was actual documented behavior of the Set.