The Blind 75 Leetcode Series: 1. Two Sum

This is a new series of work I’m gonna do for my own purpose as well as helping others, if possible.

Traditionally, when I am doing Leetcode problems, I start with a problem, try to figure out the solution by brute force, and then either I figure it out or I don’t. I then go to discussions and get frustrated by those brilliant answers. People keep saying it’s pattern recognition and repetition, but as soon as I get my offer, I throw all the knowledge and memory about the problems away.

Then the next job hunt cycle comes, and I repeat the process.

Finding a job itself is another job, and the time and energy spent on it is tremendous. This is on top of the frustration I get from all the rejections. I often get very depressed as the job hunt goes, and the moment I accept an offer, I recover. I want to shorten that amount of time.

I can’t control the pace they review my candidacy, so I can only do better at what I know is crucial: Whiteboarding, or just Leetcode, really.

I attempt to use this series to go through the Blind 75 on Leetcode. One by one with my attempts and thought process written out. Maybe it’ll help me to remember these patterns and approaches better.

Without the pressure to get a job this time, I hope I can focus more on the problem itself instead of the need to find a new job.

So here it is, first question is

  1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Let’s always start with some brute force approach. Really, sometimes that’s all interviewers are looking for, believe it or not. Maybe not FANGG (or MANGA?)-like companies, but we should at least know how to solve a problem with the most straightforward approach.

What has this problem given and what is it looking for? We have a list of integers num and a target integer target, and the problem is looking for 2 indices that the corresponding numbers add up to the target.

Usually interviewers would make the descriptions vague on purpose to see if you can identify potential confusions and corner cases. The problem is nice enough to tell us that we will ALWAYS find one set of indices as solution, so we don’t have to worry about no return. It also states that we cannot use the same number twice, so nothing like (2, 2) as solution.

The rest is very straightforward. Since it’s a list, we can iterate through it. For each integer, we find another integer that matches by looping through the rest of the list. Remember, this is the brute force approach. We just want to find A solution for now.

Since it’s asking for the indices, we can just use indices as pointers. Thus we can simply do

for i in range(0, len(num)-1):
for j in range(i, len(num)):
if num[i] + num[j] == target:
return [i, j]

This is it. We for sure will get one set of indices, so we know this returnwill always happen.

Now how does this perform. Normally when I see a problem as simple as this and then see a double for-loop, it screams for improvement. The current approach for this is O(n²) for time complexity. Let’s take a look in detail.

for i in range(0, len(num)-1):  # First for-loop, O(n)
for j in range(i, len(num)): # Second for-loop, O(n)
if num[i] + num[j] == target: # this is an O(1) operation
return [i, j]

Although the second for loop is shorter, the scale is still linear, thus O(n). The longer the list, the longer it takes to go through it and the growth rate is linear. Can we do better?

We should only go through the list once if we can’t do twice. Can we keep track of 2 numbers at the same time, so we don’t have to create another loop? We can have 2 pointers, one pointing to each number, but how would the pointers move? What’s the criteria?

We know that if the numbers are sorted, and we start from the 2 ends of the list, we can move the pointers based on the sum of the two numbers.

Let’s say the list is [1, 2, 3, 4, 5, 9] and the target is 8, we know the answer will be (2, 4) with 0-based indexing, which corresponds to 3 and 5. If we start with two ends, which are 1 and 9, the sum is 10, simply too large. How do we make the sum smaller? We move one pointer to point to a smaller number. The pointer to move is the one pointing to 9. When we move it one step to the left, now it points to 5. The sum is now 6 which is smaller than the original sum, 10.

However, the sum is now too small, so we move the left pointer instead. moving it from 1 to 2 makes the sum 7, still too small, so we move the left pointer again to 3. Now the sum is what we are looking for, so we can return the indices where these two pointers are at.

Note that we need to make sure the list is sorted in ascending order and there are only 1 pair of answer, otherwise we cannot do this kind of greedy approach.

i, j = 0, len(nums)  # find 2 indices at beginning and end
nums.sort() # make sure the list is sorted
while i < j: # when i meets j, we have checked all combinations
if nums[i] + nums[j] == target:
return i, j
elif nums[i] + nums[j] > target:
j -= 1 # move j 1 step to the left if sum is too large
else:
i += 1 # move i 1 step to the right if sum is too small

What’s the time complexity now? We only go through the list once, so it’s linear, O(n). However, because we have to make sure the list is sorted in ascending order for this approach to work, we have to sort it. The built-in sorting for Python3 is Timsort, which counts for O(n log n) for time complexity, so that raises the total time complexity to O(n log n).

i, j = 0, len(nums)
nums.sort() # O(n log n) for sorting
while i < j: # worst case, we go through the entire list, O(n)
if nums[i] + nums[j] == target:
return i, j
elif nums[i] + nums[j] > target:
j -= 1
else:
i += 1

Can we do even better? What if we don’t have to sort? If we want to do it this way, we have to keep track more than just the indices. We know that a + b should equal to the target, so target- a = b. Going back to the example of [1, 2, 3, 4, 5, 9] and target = 8, when the pointer is on 1, the difference between 1 and target is 7, so we know that we found the pair if we ever see a 7. To track these, we need to construct some sort of memory and keep feeding the information in. I choose a dict here which hold key-value pairs. I choose the key to be the difference and the value to be the index of the pointer, so the key-value pair looks like {7: 0} (if you find the diff 7, the first number is at position 0).

The code would look like this:

tracker = {}
for i, n in enumerate(nums): # enumerate yields idx, val of a list
if n in tracker: # we've seen the other number and the diff before. Return the current index and the index tracked in tracker
return (i, tracker[n])
else:
tracker[target-n] = i # track the diff and the index

This only requires us to go through the loop once, and we don’t need to sort it. Thus the time complexity becomes O(n). Much better.

tracker = {}
for i, n in enumerate(nums): # the only loop, O(n)
if n in tracker:
return (i, tracker[n])
else:
tracker[target-n] = i

Note that this does require more memory (also O(n)), but normally we don’t care as much about space complexity compare to time.

This is it! You’ve solved the first question of the Blind 75!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store