Crack Leetcode 1: Two Sum
There is a way to make it easy.
Sometimes they make it look hard, while in fact, there’s always a way you can easily understand. Today, we’ll crack leetcode 1 — Two Sum — together. Without further ado, let’s get started.
Solution:
Explain the idea:
Let’s use an example to make our thoughts clearer :
Input: nums= [2, 3, 4, 5], target=6.
Now checking the first number: 2. We are looking for (target-2), or 4; and when we found it, we want to return its “index” value.
So first of all, we need a “dictionary” to look up a certain number, next we want to return its “index” value — — and that looks like a dict{ } to me.
Solution #1. Two-Pass:
So we firstly build the whole dictionary based on input nums. Then, we go over each number in nums, and lookup its complementary number.
Why two-pass? Because building the whole dictionary requires us to go over input nums once, and checking if each number has a complement is another pass.
Corner Case:
It’s totally fine, just be careful about one case: nums=[3,2,4], target=6, and the algorithm finds you two 3. This is because when looking up complement for number3, the dictionary found number 3 itself. So we have to rule out itself when looking up complement.
Solution #2. One-Pass:
Not my first thought, but I think I can nail it next time I encountered this leetcode problem, or similar.
The idea is to look up the complement while the dictionary is still “under construction”.
When we get a new key-value, we look up the complementary key in the “incomplete” dictionary. If it’s there, job done. Otherwise, we record the new key-value into the dictionary, and continue the process.
By the time we finished building our dictionary, we surly have found the answer. That’s why it only requires one pass at most.
Python Code:
Here’s the python code for the one-pass idea:
Complexity Analysis:
Time complexity:
As looking up a value in dictionary takes a constant time, and it only has one pass, the time complexity = O(N).
Space complexity:
The auxiliary space consumption is mainly due to the dictionary. In the worst case, we have to build the whole dictionary to find the answer. Therefore the auxiliary space complexity = O(N).
and the input we know is O(N).
=>Space complexity = O(N).
The End:
Thanks for reading! Please check our articles more often, if you’d like to support our work — and we’ll see you in the next one!
