https://leetcode.com/problems/two-sum/
Problem:
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.Example:
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
What should I understand and be mindful of?
Key Points (referred to as KP# throughout the explanation):
- You must return the indices
- Exactly 1 solution
- No same elements twice
Possible Clarifying Question(s) to Ask:
- Can it have negative numbers?
- Are the numbers in the array sorted?
- Are duplicates allowed?
Generate Examples:
- nums = [2, 7, 11, 15], target = 9, ans = [0, 1]
since nums[0] + nums[1] = 2 + 7 = 9 - nums = [5, 7, -2, 10, 13, 3, 1, 8], target= 21, ans = [4, 7]
since nums[4] + nums[7] = 13 + 8 = 21
Make sure you understand the problem before moving on!
How should I approach this problem?
Brute-Force Approach:
If you were given this problem and you were not allowed to use any devices or tools (even paper & pen!), what would you do? You would naturally try to select one number from the array, and see if any other number is a complement of it! Awesome! That can be the starting point for our brute-force approach.
So how do we code that?
We will have two for-loops and check the pairs at each iteration.
Why does j start from i + 1, and not 0 like i does?
To prevent duplicate and illegal(Key Point #3) calculations. Let’s visually understand this.
j=0
i=0
[2, 7, 11, 15]
seen before: (2,2)
Earlier, we acknowledged that the same element cannot be used twice, rendering this pair illegal(KP#3). j=1
i=0
[2, 7, 11, 15]
seen before: (2,2) (2,7) j=2
i=0
[2, 7, 11, 15]
seen before: (2,2) (2,7) (2,11) j=3
i=0
[2, 7, 11, 15]
seen before: (2,2) (2,7) (2,11) (2,15)j reaches the end so j is reset back to index 0
i will be incremented by 1 to 1 j=0
i=1
[2, 7, 11, 15]
seen before: (2,2) (2,7) (2,11) (2,15), (7,2)
There is a duplicate calculation with (2,7) and (7,2). The order at which they are positioned does not matter since we are calculating the sum of the two.j=1
i=1
[2, 7, 11, 15]
seen before: (2,2) (2,7) (2,11) (2,15), (7,2), (7, 7)
Illegal(KP#3) pair here again. Or anytime we start a new iteration of pointer i.
Now, let’s take a look at how starting j at index i + 1 helps.
j=1
i=0
[2, 7, 11, 15]
checked so far: (2,7) j=2
i=0
[2, 7, 11, 15]
checked so far: (2,7) (2,11) j=3
i=0
[2, 7, 11, 15]
checked so far: (2,7) (2,11) (2,15) j=2
i=1
[2, 7, 11, 15]
checked so far: (2,7) (2,11) (2,15) (7,11) j=3
i=1
[2, 7, 11, 15]
checked so far: (2,7) (2,11) (2,15) (7,11) (7,15) j=3
i=2
[2, 7, 11, 15]
checked so far: (2,7) (2,11) (2,15) (7,11) (7,15) (11,15)DONE!
We can see above that there are no illegal (KP#3) pairs; as in, pairs of the same number.
Additionally, since j always starts from i + 1, we are cutting down on many duplicate checks. In fact, with our second diagram, we can see that after 6 iterations, we are done. With our first diagram, we are only halfway through after 6 iterations.
How should I check the two numbers?
Change this
to
We are returning not the numbers themselves, but the indices where we found them (KP #1). Additionally, it is acceptable to return the first match we get, since we acknowledged earlier that the problem can only have one solution, as in, one pair (KP#2).
What is the time and space complexity?
Time: O(n²) Why? For every index i, we are iterating over the whole array with our pointer j.
Space: (1)
How can I optimize my solution?
Let’s look at our bag of tricks:
Since we know that our brute-force approach is O(n²) time, we know that our optimal solution will be less than that. Complexities less than O(n²) would be O(1), O(logn), O(n) O(nlogn) — generally speaking. Let us keep this in mind to help ourselves come with a better solution.
Both complexities of O(1) and O(logn) imply that not every element was needed to iterate on; however, since the nature of the problem (worst-case) requires us to potentially iterate over each number in the array, we can eliminate these options. We cannot eliminate O(n) because it is necessary to visit each number and check if it can be a part of the final solution.
indices 0 1 2 3 4
nums = [1, 2, 3, 4, 5]
If our target was 9, then we would have gotten a match when we were checking the last two numbers. At that point, we have already iterated through the whole array and so our fastest algorithm will on worse-case be O(n).That leaves us with O(n) and O(nlogn). That’s great. Let’s start with O(nlogn) since solutions with higher time complexity naturally allows more inefficiency, which helps us get closer to the optimal solution in a gradual, but certain way. We don’t necessarily always want to jump straight to the optimal solution and get stuck there.
Our “Next-Best” Approach:
With O(nlogn), it immediately reminds me of sorting. Let’s try that out and sort the given input array in our generated example #2, as shown below. (Example #1 happens to be already sorted)
indices 0 1 2 3 4 5 6 7
nums = [5, 7, -2, 10, 13, 3, 1, 8]
target= 21
ans = [4, 7]
since nums[4] + nums[7] = 13 + 8 = 21will become...indices 0 1 2 3 4 5 6 7
original nums = [5, 7, -2, 10, 13, 3, 1, 8]
sorted nums = [-2, 1, 3, 5, 7, 8, 10, 13]
Now that we have a sorted array, and since we are trying to find a particular pair that sums to the target 21, we can use the two-pointer technique. (Note: the two-pointer technique is always worth considering when you are supposed to do work on a sorted array(s)) We can have a pointer called left (denoted as l ) at the start of the array and another pointer called right (denoted as r) at the end of the array. We’ll first see how the two numbers under the two pointers compare with our target. Depending on the difference, we will change the appropriate pointer so that our next guess will be closer. Let’s visualize it.
indices 0 1 2 3 4 5 6 7
l r
nums = [-2, 1, 3, 5, 7, 8, 10, 13]
sum = nums[left] + nums[right] = -2 + 13 = 11.Since 11 is less than our target, we want our next guess to be larger than 11.
How can we change the pointers to ensure that? If you look closely, decrementing our right pointer will only reduce our sum. This is because the array is sorted, and there is nothing to the right of the right pointer, and everything to the left of the right pointer is a smaller number.
What we can do instead is to increment the left pointer. Let's go ahead and do that.indices 0 1 2 3 4 5 6 7
l r
nums = [-2, 1, 3, 5, 7, 8, 10, 13]
sum = nums[left] + nums[right] = 1 + 13 = 14.Much better! We are closer to our target now. We can keep repeating this until we get our match!indices 0 1 2 3 4 5 6 7
l r
nums = [-2, 1, 3, 5, 7, 8, 10, 13]
sum = nums[left] + nums[right] = 3 + 13 = 16.indices 0 1 2 3 4 5 6 7
l r
nums = [-2, 1, 3, 5, 7, 8, 10, 13]
sum = nums[left] + nums[right] = 5 + 13 = 18.indices 0 1 2 3 4 5 6 7
l r
nums = [-2, 1, 3, 5, 7, 8, 10, 13]
sum = nums[left] + nums[right] = 7 + 13 = 20.indices 0 1 2 3 4 5 6 7
l r
nums = [-2, 1, 3, 5, 7, 8, 10, 13]
sum = nums[left] + nums[right] = 8 + 13 = 21.We got our match!
Before we go ahead and submit your solution, can you see a problem?
As per KP#1, we must return the indices.
How do we keep track of the indices while sorting?
One solution to this problem would be to keep track of the indices that the numbers were found before we sort the array. Here, I will use a tuple to keep track.
nums = [5, 7, -2, 10, 13, 3, 1, 8]for i, num in enumerate(nums):
nums[i] = (num, i)nums = [(5,0), (7,1), (-2,2), (10,3), (13,4), (3,5), (1,6), (8,7)]nums.sort(key=lambda x: x[0])Using our information above, our final solution will be as below.
What is the time and space complexity?
Time: O(nlogn)
Space: (1)
Now to our O(n) time & O(n) space complexity solution
Can we do better? Yes! As we discussed earlier, we still have the O(n) option to explore.
In the beginning, I asked how you would solve this problem if you did not have any tools such as a pen & paper. Because of that, you might have had to look at the numbers a few different times when you were trying to find a complement number because you forgot the numbers you have already encountered. That inefficiency due to the back-and-forth essentially mimics the nested for-loop we had earlier.
Now what if I asked the same question but this time, you get to have a pen & paper, and you are allowed to look through each number only once?
If I were you, I’d naturally start looking at the numbers one by one, and note down which numbers I have seen in the past.
Congratulations! You have just found a O(n) solution!
In code, this would mean that for every number we visit, see if there is a complement in our list of numbers we’ve already visited. If we find a complement, and thus a match, we return the indices of those two numbers.
indices 0 1 2 3 4 5 6 7
i
nums = [5, 7, -2, 10, 13, 3, 1, 8]
is target - number or 21 - 5 or 16 in seenBefore? NO
seenBefore = {}
target= 21
ans = [4, 7]indices 0 1 2 3 4 5 6 7
i
nums = [5, 7, -2, 10, 13, 3, 1, 8]
seenBefore = {5: 0}
is target - number or 21 - 7 or 14 in seenBefore? NOindices 0 1 2 3 4 5 6 7
i
nums = [5, 7, -2, 10, 13, 3, 1, 8]
seenBefore = {5: 0, 7: 1}
is target - number or 21 + 2 or 23 in seenBefore? NOindices 0 1 2 3 4 5 6 7
i
nums = [5, 7, -2, 10, 13, 3, 1, 8]
seenBefore = {5: 0, 7: 1, -2: 2}
is target - number or 21 - 10 or 11 in seenBefore? NOindices 0 1 2 3 4 5 6 7
i
nums = [5, 7, -2, 10, 13, 3, 1, 8]
seenBefore = {5:0, 7:1, 10:3}
is target - number or 21 - 13 or 8 in seenBefore? NOindices 0 1 2 3 4 5 6 7
i
nums = [5, 7, -2, 10, 13, 3, 1, 8]
seenBefore = {5:0, 7:1, 10:3, 13:4}
is target - number or 21 - 3 or 18 in seenBefore? NOindices 0 1 2 3 4 5 6 7
i
nums = [5, 7, -2, 10, 13, 3, 1, 8]
seenBefore = {5:0, 7:1, 10:3, 13:4, 3:5}
is target - number or 21 - 1 or 20 in seenBefore? NOindices 0 1 2 3 4 5 6 7
i
nums = [5, 7, -2, 10, 13, 3, 1, 8]
seenBefore = {5:0, 7:1, 10:3, 13:4, 3:5, 1:6}
is target - number or 21 - 8 or 13 in seenBefore? YESreturn [seenBefore[number], i]
return [4, 7]
One of important things to consider when solving coding problems is the time-space complexity trade-off. The first 2 solutions we discussed had O(1) space complexity, since we didn’t have any pen & paper, or memory. Now that we were given more memory and space (in the form of pen & paper), we can utilize that to lower our time complexity (by reducing the # of times needed to check the numbers).
To summarize, the three solutions we discussed today are:
- Using nested for-loop (brute-force) O(n²) | O(1)
- Using two pointers w/ sort O(nlogn) | O(1)
- Using a dictionary / hash table O(n) | O(n)
