LeetCode Python TwoSums

Question

I am absolutely a noob on python, and just started to practice on leetcode. Anyway take a look at this TwoSum exercise: Given an array of integers, find two numbers such that they add up to a specific target number.

Here is my code for this exercise:

class Solution(object):

    def __init__(self, nums, target):
        self.nums = nums
        self.target = target

    def twoSum(self):
        for i in range(len(self.nums)):
            for j in range(i+1, len(self.nums)):
                if self.nums[i] + self.nums[j] == self.target:
                    print "index1=" + str(i) + ", index2=" + str(j)

sample = Solution([2, 8, 7, 15], 9)
sample.twoSum()

Anyone can help me how should the leetcode algorithm answer be look like? Will this one be OK for an interview? Thanks

Answer 1

I wouldn't consider your code or the itertools solution acceptable, because they are both O(n^2). If given in an interview, the interviewer probably wants to see that you can do better than just running two nested for loops.

I would use a hash table or sort the array and then binary search the answer.

Hash table pseudocode

h = empty hash table
for each element e in array
  if target - e in hash table:
    we have a solution
  add e to hash table

This will have complexity O(n), subject to some hash table quirks: in the worst case, it can be O(n^2), but that shouldn't happen for random inputs.

Binary search pseudocode

sort array
for each element e in array
  binary search for target - e, make sure it's not found at the same index
  if it is, check the before / after element

  or think how you can avoid this happening

This will always be O(n log n).

If complexity doesn't matter, then the itertools solution is nice, but your code also gets the job done.