DEV Community

loading...

Discussion on: Daily Challenge #273 - Remove Duplicates

Collapse
jpantunes profile image
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;
}
Collapse
vinaypai profile image
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.

Collapse
jpantunes profile image
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!

Thread Thread
vinaypai profile image
Vinay Pai

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