## DEV Community # 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! 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]
`````` Grégoire Welraeds

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

``````def Remove(duplicate):
final = []

for i in range(len(duplicate)):
if duplicate[i] not in duplicate[i+1:]:
final.append(duplicate[i])

return final

x = input("Enter the integers: ")
x = x.split()

print(Remove(x))

`````` 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;
return array;
};

`````` 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

``````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. Akash Kava

You are forgetting OLog(n) steps used by IntMap internally, it is never O(n), Valts Liepiņš

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

Here, in `Map` documentation most lookup and insertion operations are indeed `O(log n)`:

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):

This effectively means that after `IntMap` contains more than 64 elements, the time complexity is constant `O(W)` or `O(1)`. 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. JP Antunes • Edited

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. open
``````
function solve(list) {
return list.filter((a, b) => array.indexOf(a) == b)
};

`````` 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)
`````` ## 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);
}
`````` ``````(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. Grégoire Welraeds

`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) Rafael Acioly

Python 🐍

``````from typing import List

def solve(nums: List[int]): List[int]:
return list(set(nums))
``````