## 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.

loading...

# Discussion on: Daily Challenge #273 - Remove Duplicates

## Replies for: Haskell module Main where deduplicate :: [Int] -> [Int] deduplicate [] = [] deduplicate (x:xs) | elem x xs = deduplicate xs | otherw...

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

Thread
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
Akash Kava

Interesting .. I wasn't aware of that.