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.