How much interesting the simplest leetcode problem could be?
Even the simplest Leetcode problem could teach you a lot. And this is my story.
Problem
Let's checkou the problem first.
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Principle
During the solving and optimizing procedure, make sure you have utilized ALL the conditions provided by the problem. Yes, all of them.
Brute Force
If you don't know much about the problem, the best way of solving the problem is by writing some code intuitively, especially for this kind of simple one.
So my first try is just a Swift translation of the problem:
/// Solution 1
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var i = 0
var j = i + 1
for n in i ..< nums.count - 1 {
for m in j ..< nums.count {
if nums[n] + nums[m] == target {
return [n, m]
}
}
i += 1
j = i + 1
}
return [0, 0]
}
The implementation is quite straightforward. We add nums[n] with each element in the rest of num. If the sum equals target, return [n, m] directly, or return [0, 0] for an empty match (The problem do not specify how to handle errors).
- The time complexity of this brute force approach is
O(n^2); - The space complexity is
O(1);
If we try to submit this answer to Leetcode, we will get the following result:
Every experienced programmer knows that an O(n^2) algorithm should be avoided.
Optimize the complement query process
In order to optimize the algorithm, we need to understand why its time complexity is O(n^2): When trying to find the complement of num[n], we need to iterate through the rest of num which is an O(n) process. If we can optimize it to O(1), the whole time complexity will down to O(n).
As we know, fetch elements from a dictionary is an O(1) algorithm. So this is my first optimization:
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
let lookup: [Int: Int] = Dictionary(uniqueKeysWithValues: nums.enumerated())
for (i, v) in nums.enumerated() {
if let (index, _) = lookup.first { $0.1 + v == target } else {
return [i, index] }
}
}
return [0, 0]
}
Quite understandable, right? I try to build a Dictionary which is keyed by each index of the element of num, then traverse num and find a possible complement through lookup. But unfortunately, this would not compile and I got serveral compile errors which make me know more about Swift.
A bug of EnumeratedSequence
The first, Dictionary(uniqueKeysWithValues: nums.enumerated()) won't compile. The compiler complains that: Generic parameter 'Key' could not be inferred. But even if you specifiy the Key and Value explicitly:
Dictionary<Int, Int>(uniqueKeysWithValues: nums.enumerated())
You will get a more wiered error: Generic parameter 'S' could not be inferred. Emm... Actually, I don't know what's the the generic parameter S. But after googling this problem, I found a thread on on official Swift forum and a bug of SR-6305 talking about this problem.
Simply speaking, the core problem is that the element type of EnumeratedSequence, which is returned by enumerated, is a tuple with tags like this:
typealias Element = (offset: Int, element: Base.Element)
This is why Dictionary<Key, Value>(uniqueKeysWithValues:) cannot extract values from it to build a Dictionary. The interesting here is that the following code works:
let r1 = [(offset: 0, element: 1), (offset: 1, element: 2)]
let dict1 = Dictionary(uniqueKeysWithValues: r1) // [1:2, 0:1]
But this failed:
let r2 = [1, 2].enumerated()
let dict2 = Dictionary(uniqueKeysWithValues: r2)
// Error: Generic parameter 'Key' could not be inferred
Currently, the workaround is map r2 to an [(offset: Int, element: Int)]:
let r2 = [1, 2].enumerated().map { $0 }
let dict2 = Dictionary(uniqueKeysWithValues: r2) // [1:2, 0:1]
But actually, I don't like this workaround, it's verbose. Since the EnumeratedSequence doesn't work, we can build a similar data structure by zip：
let r3 = zip(0..., [1, 2])
let dict3 = Dictionary(uniqueKeysWithValues: r3)
And it looks much better.
Cannot use trailing closure syntax in a if let expression
This is my second optimization:
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
let lookup: [Int: Int] = Dictionary(uniqueKeysWithValues: zip(0..., nums))
for (i, v) in nums.enumerated() {
if let (index, _) = lookup.first { $0.1 + v == target } else {
return [i, index] }
}
}
return [0, 0]
}
And I failed again because we cannot use trailing closure syntax inside a if let expression. Compiler will match the first { as the open brace for if let, not the first function. You have to put it inside the calling:
for (i, v) in nums.enumerated() {
if let (index, _) = lookup.first(where: { $0.1 + v == target }) else {
return [i, index] }
}
}
But I like the trailing closure style and update the for loop like this:
for (i, v) in nums.enumerated() {
let elem = lookup.first { $0.value == (target - v) }
if let (index, _) = elem { return [i, index] }
}
If you submit this to Leetcode, you will be blocked by a testcase like this:
twoSum([3, 2, 4], 6)
The expected result is [1, 2], but our implementation returns [0, 0]. This is because 3 + 3 = 6 and the index returned by lookup.first { $0.value == (target - v) } is exactly the same as the element we currently traversed. This is why the problem requires that you may not use the same element twice. So except for checking elem is not nil, we have to check the index is not equal to i. And this is my semi final version:
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
let lookup: [Int: Int] = Dictionary(uniqueKeysWithValues: zip(0..., nums))
for (i, v) in nums.enumerated() {
let elem = lookup.first { $0.value == (target - v) }
if let (index, _) = elem, index != i { return [i, index] }
}
return [0, 0]
}
But after submitting to Leetcode, I failed again. Yes again! My implementation was out of time limiting. The only explanation might be creating a Dictionary from a zipped sequence is not as efficient as I expected.
But the initial direction is still right. We need to reduce the time complexity of the complement number query.
What can we do next?
Final optimization
The idea is we can combine the first two version of twoSum. While we iterate num, we add the element into lookup. We also check if the complement is already in the lookup. If it exists, we get the answer immediately:
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var lookup: [Int: Int] = [:]
for (i, v) in nums.enumerated() {
if let index = lookup[target - v] {
return [index, i]
}
lookup[v] = i
}
return [0, 0]
}
Submit this to Leetcode, and it's improved greatly:
Swift vs CPP
At the end of this article, let compare C++ version of the same algorithm against Swift:
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> record;
for (int i = 0; i < nums.size(); ++i) {
int complement = target - nums[i];
auto pos = record.find(complement);
if (pos != record.end()) {
return vector { pos->second, i };
}
record[nums[i]] = i;
}
return vector<int> {};
}
And it's three times faster and half of memory requirement than Swift:
Things to remember
Write them down inside a card and it will help you recap the problem very quickly:
- Write some code intuitively first, do try to make every thing perfect at a single shot;
- Make sure you have check ALL the conditions and requirements the problem provided;
- Optimizing an
O(n^2)algorithm could be started by reduce the time complexity of a inner loop; - Matching a sum of
m + nis just another phase of finding the complement ofm; - You cannot use trailing closure syntax inside a
if letexpression in Swift; - Swift is still far more slow and expensive than C++ (LoL, just for fun, it doesn't mean C++ is better than Swift);