In this challenge, you will remove the left-most duplicates from a list of integers and return the result.
// Remove the 3's at indices 0 and 3
// followed by removing a 4 at index 1
solve([3, 4, 4, 3, 6, 3]); // => [4, 6, 3]
Tests:
solve([3,4,4,3,6,3])
solve([1,2,1,2,1,2,3])
solve([1,1,4,5,1,2,1])
solve([1,2,1,2,1,1,3])
Good luck!
This challenge comes from KenKemau on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!
Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!
Latest comments (30)
Here's my python solution
O(n)
. The idea is to iterate over the input and keep track of the index of the last time you saw a given number. If you see a number, replace the old value withNone
, and do a second pass at the end to remove all theNone
s.The two-phase approach is necessary to keep it
O(n)
. If we remove items as we find them it could end up costingO(n^2)
.pprint(solved)
set([3, 4, 6])
is not
[4,6,3]
which is the expected answer (you only keep the last occurrence of each duplicates, not the first)
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.
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.
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!
Good to know, I didn't know that was actual documented behavior of the Set.
javascript
The question remains, does the
for in
kill the man what if it sorts lexically and not numerically? Should I have justfor (const x of sparse) if (typeof x !== "undefined") out[o++] = x
?Maybe
ayy lmao
is
[3, 4, 6]
not
[4, 6, 3]
To get the correct result you'd have to do
which is... quite a lot.
Here is the simple solution with PHP:
Haskell
Test
Wouldn't this have
O(n^2)
time complexity? This could be done inO(n)
, using aIntMap
.EDIT:
This is my attempt at writing a similar function but with
O(n)
time complexity (O(n*m)
whenm <= 64
, wherem
is amount of elements inIntSet
):You are forgetting OLog(n) steps used by IntMap internally, it is never O(n),
Perhaps you're mistaking
IntMap
forMap
?Here, in
Map
documentation most lookup and insertion operations are indeedO(log n)
:hackage.haskell.org/package/contai...
But in
IntMap
documentation, you can see that the actual complexity isO(min(n, W))
, where W is size of integer type (32 or 64):hackage.haskell.org/package/contai...
This effectively means that after
IntMap
contains more than 64 elements, the time complexity is constantO(W)
orO(1)
.Interesting .. I wasn't aware of that.
Hi and thanks for your reply. This looks like a very good solution.
Indeed this algorithm would have an
O(n²)
time complexity if thexs
list would remain the same. I believe the time complexity isO(n log n)
since we are decreasing thexs
list each time in the solution I proposed. But I'm bad at time complexity so I wouldn't know.I didn't know about
Data.IntSet
I'll look into that. Thanks for sharing.Python 🐍
Javascript in O(n) (more specifically
3n
, looping three times on the length of the input, two identicalreduce
es and onefilter
):Epic, but also this relies on the
array
being sparse in the first reduce (so, a map really), sincenew Array(Number.MAX_SAFE_INTEGER)
is an error.I'd express that as
which is just a funny version of
Here Goes, My Solution
In JavaScript (ES6)
const originalArray = [3,4,4,3,6,3];
const distinctArray = [...new Set(originalArray)];
Nope
In C with O(n2):
Cool!
Thanks, I am new to Programming.
Nim:
This solution is in python
output
is
[3, 4, 6]
not
[4, 6, 3]
which is the expected answer
Fixed it
Hi, you could have use the
set
method, like this:dev.to/rafaacioly/comment/12l2j
:)