## DEV Community is a community of 638,993 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading... # Daily Challenge #273 - Remove Duplicates

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!

## Discussion (33) Deepak Raj • Edited

`This solution is in python`

``````def Remove(duplicate):
final_list = []
for num in duplicate:
if num not in final_list:
final_list.append(num)
return final_list

print(Remove([3, 4, 4, 3, 6, 3]))
``````

output

``````[3, 4, 6]
`````` Nathan Kallman • Edited

Javascript in O(n) (more specifically `3n`, looping three times on the length of the input, two identical `reduce` es and one `filter`):

``````const identity = (i) => i || i === 0;
const radixPush = (array, radix, value) => {
array[radix] = value;
return array;
};

const solve = (array) => array.reduce(radixPush, []).reduce(radixPush, []).filter(identity);
`````` Mihail Malo • Edited

Epic, but also this relies on the `array` being sparse in the first reduce (so, a map really), since `new Array(Number.MAX_SAFE_INTEGER)` is an error.

I'd express that as

``````const solve = arr => {
const vals = new Map(function * () {for (let i=0; i < arr.length; i++) yield [arr[i], i]} ())
const out = new Array(arr.length)
for (const [v, i] of vals) out[i] = v
return out.filter(x => typeof x !== "undefined")
}
``````

which is just a funny version of

``````const solve = arr => {
const vals = new Map() // tfw no Map::with_capacity
for (let i=0; i < arr.length; i++) vals.set(arr[i], i)
const out = new Array(arr.length)
for (const [v, i] of vals) out[i] = v
return out.filter(x => typeof x !== "undefined")
}
`````` Amin

Haskell

``````module Main where

deduplicate :: [Int] -> [Int]
deduplicate [] = []
deduplicate (x:xs)
| elem x xs = deduplicate xs
| otherwise = x : deduplicate xs

main :: IO ()
main = do
print \$ deduplicate [3, 4, 4, 3, 6, 3]      -- [4, 6, 3]
print \$ deduplicate [3, 4, 4, 3, 6, 3]      -- [4, 6, 3]
print \$ deduplicate [1, 2, 1, 2, 1, 2, 3]   -- [1, 2, 3]
print \$ deduplicate [1, 1, 4, 5, 1, 2, 1]   -- [4, 5, 2, 1]
print \$ deduplicate [1, 2, 1, 2, 1, 1, 3]   -- [2, 1, 3]
``````

Test Valts Liepiņš • Edited

Wouldn't this have `O(n^2)` time complexity? This could be done in `O(n)`, using a `IntMap`.

EDIT:

This is my attempt at writing a similar function but with `O(n)` time complexity (`O(n*m)` when `m <= 64`, where `m` is amount of elements in `IntSet`):

``````import Data.Foldable (foldl')
import Data.IntSet   (empty, insert, notMember)

deduplicate :: [Int] -> [Int]
deduplicate = fst . foldl' takeUniq ([], empty) . reverse
where
takeUniq (xs, set) x
| notMember x set = (x:xs, insert x set)
| otherwise       = (xs, set)
`````` Amin • Edited

Hi and thanks for your reply. This looks like a very good solution.

Wouldn't this have O(n^2) time complexity?

Indeed this algorithm would have an `O(n²)` time complexity if the `xs` list would remain the same. I believe the time complexity is `O(n log n)` since we are decreasing the `xs` 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. Valts Liepiņš

Perhaps you're mistaking `IntMap` for `Map`?

Here, in `Map` documentation most lookup and insertion operations are indeed `O(log n)`:
hackage.haskell.org/package/contai...

But in `IntMap` documentation, you can see that the actual complexity is `O(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 constant `O(W)` or `O(1)`.

Thread Sourabh Choure

In C with O(n2):

``````#include <stdio.h>

int solve(int* nums,int* newnums, int numsSize){
if(numsSize==0){
return 0;
}

int count = 0;

for(int i=0;i<numsSize;i++){
int flag = 0;
for(int j=0;j<count;j++){
if(nums[i]==newnums[j]){
flag = 1;
break;
}
}
if(flag == 0){
newnums[count++] = nums[i];
}
}

return count;
}

int main(void)
{
int ar[] = {1,2,1,2,1,1,3};
int n = sizeof(ar)/sizeof(ar);
int newar[n];
int len = solve(ar,newar,n);

for(int i=0;i<len;i++){
printf("%d ",newar[i]);
}
printf("\n");
return 0;
}
`````` JP Antunes • Edited

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. Vinay Pai

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 with `None`, and do a second pass at the end to remove all the `None`s.

The two-phase approach is necessary to keep it `O(n)`. If we remove items as we find them it could end up costing `O(n^2)`.

``````def solve(arr):
last_seen = {}
res = []

for val in arr:
if val in last_seen:
res[last_seen[val]] = None
last_seen[val] = len(res)
res.append(val)

return list(v for v in res if v is not None)
`````` Mihail Malo • Edited

## javascript

``````const solve = arr => {
const vals = new Map()
for (let i=0; i < arr.length; i++) vals.set(arr[i], i)
const sparse = new Array(arr.length)
for (const [v, i] of vals) sparse[i] = v
const out = new Array(vals.length)
let o = 0;
for (const i in sparse) out[o++] = sparse[i]
return out
}
``````

The question remains, does the `for in` kill the man what if it sorts lexically and not numerically? Should I have just `for (const x of sparse) if (typeof x !== "undefined") out[o++] = x`?

Maybe

``````function * isDef(it) {
for (const x of it) if (typeof x !== "undefined") yield x
}
const solve = arr => {
const vals = new Map() // tfw no Map::with_capacity
for (let i=0; i < arr.length; i++) vals.set(arr[i], i)
const sparse = new Array(arr.length)
for (const [v, i] of vals) sparse[i] = v
const out = new Array(vals.length)
const search = isDef(sparse)
for (let i = 0; i < vals.length; i++) out[i++] = search.next()
return out
}
``````

ayy lmao peter279k

Here is the simple solution with PHP:

``````function solve(\$arr) {
\$ansArr = [];

\$index = count(\$arr)-1;
for(; \$index >= 0; \$index--) {
if (in_array(\$arr[\$index], \$ansArr) == false) {
\$ansArr[] = \$arr[\$index];
}
}

return array_reverse(\$ansArr);
}
`````` Mihail Malo
``````(a => [...new Set(a)])([3, 4, 4, 3, 6, 3])
``````

is
`[3, 4, 6]`
not
`[4, 6, 3]`

To get the correct result you'd have to do

``````[...new Set(a.reverse())].reverse()
``````

which is... quite a lot.