Discussion on: Daily Challenge #273 - Remove Duplicates

View post

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ņš • Jul 28 '20 • 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 • Jul 28 '20 • 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 • Jul 29 '20

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

Valts Liepiņš • Jul 29 '20

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

Akash Kava • Jul 29 '20

Interesting .. I wasn't aware of that.