Two Sum Problem:
Given an array of integers A and an integer K return True if there are two elements two elements xi, xj (i != j) such that xi + xj = K. Return False otherwise.
I am implementing the classical two sum problem but I am currently practising Functional programming so I picked Haskell. I wrote a naive implementation which I expect is O(n²) (not sure though).
In the brute force implementation I just try every pair of numbers until I find the ones that meet the criteria;
-- O(n^2) implementation twoSum :: [Int] -> Int -> Bool twoSum  k = False twoSum (x:) k = False twoSum (x:y:) k = k == x + y twoSum (x:y:xs) k | k == x + y = True | otherwise = twoSum (x:xs) k || twoSum (y:xs) k
Then I tried to optimize it. I use a Set to store seen numbers, and then traverse every element x of the array. If K - x is in the Set, it means I found the pair that satisfies the condition.
Per my analysis I think the time complexity is O(n log n) because set implementation in Haskell is O(log n) in insert and check membership:
import qualified Data.Set as S import Prelude -- O(n log n) Implementation twoSumOpt:: [Int] -> Int -> Bool twoSumOpt  k = False twoSumOpt (x:) k = False twoSumOpt (x:y:) k = k == x + y twoSumOpt (x:y:xs) k | k == x + y = True | otherwise = twoSum' (y:xs) k (S.insert x seen) where seen = S.fromList() twoSum' :: [Int] -> Int -> S.Set Int -> Bool twoSum' (x:) k s = S.member (k - x) s twoSum' (x:y:) k s = k == x + y twoSum' (x:xs) k s | S.member (k - x) s = True | otherwise = twoSum' xs k (S.insert x s)
I tested with some inputs and profiled solutions:
ghci> twoSumOpt [1, 2, -4, 3, 5, -7, 8] (-2) True (0.01 secs, 892,912 bytes) ghci> twoSumOpt [1..10000000] 10000001 True (8.51 secs, 8,154,041,496 bytes) ghci> twoSumOpt [1..100000000] 100000001 True (95.83 secs, 91,669,673,632 bytes)
Question: am I following the correct Haskell patterns? (the
O(N²) implementation didn't finish with my inputs so I assume I got the improvement in performance).
And finally, can we do better in Haskell? Is there a way to implement an amortized insertion and lookup of O(1) so I can do this in O(N)?