DEV Community

loading...

Discussion on: Daily Challenge #273 - Remove Duplicates

Collapse
cipharius profile image
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)
Collapse
aminnairi profile image
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.

Collapse
akashkava profile image
Akash Kava

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

Thread Thread
cipharius profile image
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 Thread
akashkava profile image
Akash Kava

Interesting .. I wasn't aware of that.