0015 3Sum

Solved at: 2023-01-30 3Sum - LeetCode

Question

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Solution

class Solution {
    func threeSum(_ numsOriginal: [Int]) -> Int {
        var map = [Int: [(Int, Int)]]()

        var counter = [Int: Int]()

        for (i, x) in numsOriginal.enumerated() {
            if counter.keys.contains(x) {
                counter[x] = min(3, counter[x]! + 1)
            } else {
                counter[x] = 1
            }
        }

        var nums : [Int] = []

        for (i, (key, val)) in counter.enumerated() {
            for i in 0..<val {
                nums.append(key)
            }
        }

        for (i, x) in nums.enumerated() {
            for j in (i+1) ..< nums.count {
                if !map.keys.contains(nums[i] + nums[j]) {
                    map[nums[i] + nums[j]] = [(i, j)]
                } else {
                    map[nums[i] + nums[j]]!.append((i, j))
                }
            }
        }

        var set = Set<[Int]>()

        for (i, val) in nums.enumerated() {
            if map.keys.contains(0 - val) {
                let candidates = map[0 - val]!
                for candidate in candidates {
                    let (first, second) = candidate
                    if first != i && second != i {
                        var ans = [nums[first], nums[second], nums[i]]
                        ans.sort {$0 < $1}
                        set.insert(ans)
                    }
                }
            }
        }
        return Array(set)
    }
}

Results

• Time taken: 30 m 39 s
• Runtime 2424 ms, Beats 10.20%
• Memory 156.2 MB, Beats 6.9%

Complexity Analysis

$O(N^2)$ for both, worst case. $O(N^2)$ for both, worst case.