Leetcode Bootcamp — Two Sum I (Best Explanation)

To kick off the Leetcode Bootcamp we’re going to start off with a fairly simple problem that is asked all the time at companies such as Facebook, Amazon, Apple, Microsoft, and Google. This question is very commonly asked for internships and more junior software engineering positions, but none the less it is an interesting problem that should be taken seriously.

Lets begin…

Source: http://bit.ly/2JOPc4F

Problem Statement:

Given an array of numbers return the indices of the two numbers that add up to a specific target.

Assumptions:

• Let’s assume that there is one and only one solution per target.
• We can safely assume that the array is unsorted.

Restrictions:

• You cannot use the same element twice. Therefore the solution must be a set.

Edge Cases:

• #1 — What if the array is empty? We can ignore this edge case since the instructions let us assume that there is one solution. However, we can add this to our code to handle this case.

if len(nums) == 0: 
  print(“invalid input”)
  return

• #2 — What if there are negative numbers? We don’t care about negative numbers since it should not affect anything in our algorithm what so ever.
• #3 — What if we have all 0’s or some other number? We can’t use the same element twice so this would just cause us to fill the dictionary once and then we’d be done.
• #4 — What if there were non-numeric values in the list? The instruction are clear that there are only numbers in the array so this is not something to worry about. However, we can add this code snippet to our solution to handle that case properly.

for element in list:
  if not isinstance(element, int):
    print("invalid value")
    return

Approach 1 (Brute Force):

• We can do a brute force approach to this problem which would work, but, it is a very exhaustive since it requires a nested for loop, thus making our solution have the following spec: