## DEV Community is a community of 674,199 amazing developers

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

# Discussion on: Daily Challenge #273 - Remove Duplicates

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