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

The following code is doing the task in two passes which is O(n) by adding all the numbers to a dictionary (pass I) and then going over the number one-by-one and looking up the complementary number in the dictionary (pass II):

class Solution(object):

    def __init__(self, nums, target):
        self.nums = nums
        self.target = target
        self.hash = {}
        for num in nums:
            self.hash[num] = num

    def twoSum(self):
        for i in range(len(self.nums)):
            if self.hash[self.target- self.nums[i]]:
                return [self.nums[i], self.hash[self.target - self.nums[i]]]
        else:
            return False

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

Answer 2

try this code:

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
    l=[]
    for i in range(len(nums)):
        for j in range(i+1,len(nums)):
            if nums[i]+nums[j]==target:
                l.append(i)
                l.append(j)
                break
        if len(l)>0:
            break
    return l

Answer 3

C++

  
class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> numToIndex;

    for (int i = 0; i < nums.size(); ++i) {
      if (numToIndex.count(target - nums[i]))
        return {numToIndex[target - nums[i]], i};
      numToIndex[nums[i]] = i;
    }
    throw;
  }
};
                                    

C++

  
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> umap;
        int difference;

        for(int i = 0; i < nums.size(); i++ ){
            difference = target - nums.at(i);
            if(umap.find(difference) != umap.end()) {
                vector<int> v{umap[difference], i};
                return v;
            } else {
                umap[nums.at(i)] = i;
            }
        }

        return vector<int> {};
    }
};
                                    

C++

  
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        vector<int> result;
        for (int i=0; i<nums.size(); i++) {
            if ( m.find(target - nums[i]) == m.end() ) {
                m[nums[i]] = i;
            }else{
                result.push_back(m[target - nums[i]]);
                result.push_back(i);
            }
        }
        return result;
    }
};
                                    

C++

  
class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target) {
        unordered_map<int, int> index_map;

        for (int index = 0;; index++) {
            auto iter = index_map.find(target - nums[index]);

            if (iter != index_map.end())
                return vector<int> {index, iter -> second};

            index_map[nums[index]] = index;
        }
    }
};
                                    

C

  
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
*returnSize=2;
int *arr=(int *)malloc((*returnSize)*sizeof(int));
for(int i=0;i<numsSize;i++){
for(int j=i+1;j<numsSize;j++){
if(nums[i]+nums[j]==target){
arr[0]=i;
arr[1]=j;
break;
}
}
}
return arr;
}
                                    

JAVA

class Solution {
  public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> numToIndex = new HashMap<>();

    for (int i = 0; i < nums.length; ++i) {
      if (numToIndex.containsKey(target - nums[i]))
        return new int[] {numToIndex.get(target - nums[i]), i};
      numToIndex.put(nums[i], i);
    }

    throw new IllegalArgumentException();
  }
}
                                    

JAVA

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] indices = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int index = 0; index < nums.length; index++) {
            if (map.containsKey(target - nums[index])) {
                indices[1] = index;
                indices[0] = map.get(target - nums[index]);
                return indices;
            }
            map.put(nums[index], index);
        }
        return indices;
    }
}
                                    

JAVA

class Solution {
    public int[] twoSum(int[] nums, int target) {
    if(nums==null || nums.length<2)
        return new int[]{0,0};
 
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for(int i=0; i<nums.length; i++){
        if(map.containsKey(nums[i])){
            return new int[]{map.get(nums[i]), i};
        }else{
            map.put(target-nums[i], i);
        }
    }
 
    return new int[]{0,0};
    }
}
                                    

Python

class Solution:
       def twoSum(self, nums: List[int], target: int) -> List[int]:
        x = len(nums)
        for i in range(x-1):
            for j in range(1,x):
                if i == j:
                    continue
                if nums[i] + nums[j] == target:
                    return [i,j]
                                    

Python

class Solution:
    def twoSum(self, nums, target):
        length = len(nums)
        for i in range(length):
            for j in range(i + 1, length):
                if nums[i] + nums[j] == target:
                    return [i, j]
                                    

Python

class Solution:
    def twoSum(self, nums, target):
        index_map = {}
        for index, num in enumerate(nums):
            if target - num in index_map:
                return index_map[target - num], index
            index_map[num] = index
                                    

Python

class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    numToIndex = {}

    for i, num in enumerate(nums):
      if target - num in numToIndex:
        return numToIndex[target - num], i
      numToIndex[num] = i
                                    

javascript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    // Array to store the result
    result = [];
    // Map to store the difference and its index
    index_map = new Map();
    // Loop for each element in the array
    for (let i = 0; i < nums.length; i++) {
        let difference = target - nums[i];
        if (index_map.has(difference)) {
            result[0] = i;
            result[1] = index_map.get(difference);
            break;
        } else {
            index_map.set(nums[i], i);
        }
    }
    return result;
};
                                    

GOlang

func twoSum(nums []int, target int) []int {
    record := make(map[int]int)

    for index, num := range nums {
        difference := target - num
        if res, ok := record[difference]; ok {
            return []int{index, res}
        }
        record[num] = index
    }

    return []int{}
}
                                    

Kotlin

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
    // Array to store result
    val result = IntArray(2)
    // This map will store the difference and the corresponding index
    val map: MutableMap<Int, Int> = HashMap()
    // Loop through the entire array
    for (i in nums.indices) {
        // If we have seen the current element before
        // It means we have already encountered the other number of the pair
        if (map.containsKey(nums[i])) {
            // Index of the current element
            result[0] = i
            // Index of the other element of the pair
            result[1] = map[nums[i]]!!
            break
        } else {
            // Save the difference of the target and the current element
            // with the index of the current element
            map[target - nums[i]] = i
        }
    }
    return result
}
}
                                    

You can ask me any question if you don't understand the solution

Answer 4

There were Binary Search suggestions mentioned in other answers, but there was no implementation for them. So I decided to do this.

First I sort array of numbers and then do a binary search. For each number n I binary-search for target - n in sorted array.

Overall time complexity is O(N * Log(N)).

Try it online!

def two_sums(nums, target):
    def binary_search(f, a, b):
        while a < b:
            m = (a + b) // 2
            if f(m):
                b = m
            else:
                a = m + 1
        assert a == b and f(a), (a, b, f(a))
        return a

    nums = sorted(enumerate(nums), key = lambda e: e[1])

    for i, n in nums:
        begin, end = [
            binary_search(lambda j: j >= len(nums) or
                fcmp(nums[j][1], target - n), 0, len(nums))
            for fcmp in [lambda a, b: a >= b,    lambda a, b: a >  b]
        ]
        for j in range(begin, end):
            if nums[j][0] != i:
                return sorted([nums[j][0], i])

print(two_sums([2, 8, 7, 15], 9))

Output:

[0, 2]

Answer 5

a = {}
    i = 0
    while i < len(nums):
        if nums[i] not in a.values():
            a[i] = target - nums[i]
        else:
            
            keys = list(a.keys())
            vals = list(a.values())
            key = keys[vals.index(nums[i])]
            return [i,key]
        i += 1
    
    return

Using a dictionary you could solve in better time complexity

Answer 6

I have used a dictionary to store value/index as searching for a key in a dictionary can be done in O(1).

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict_nums = dict()
        for index, value in enumerate(nums):
            reminder = target - value
            if reminder in dict_nums:
                return [dict_nums[reminder], index]
            dict_nums[value] = index

Time complexity: O(n)
Space complexity: O(n)

Answer 7

The thing is many interviewers ask to solve the problem in O(n) time complexity. Here is a tip:- if interviewers ask you to reduce time complexity from O(n^2) to O(n) or O(n^3) to O(n^2) you can guess that you have to use hash table in such case for 60% of the time. You can easily solve the twoSum problem using hash table (in python it is called dictionary) to solve it. Here is my solution of the problem in python which is 94% faster than accepted ones:-

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:   
        l = len(nums)
        my_dic = {}
        
        for i in range(l):
            t = target - nums[i]
            v=my_dic.get(t,-1)
            
            if v!=-1:
                if my_dic[t]!=i:
                    return [my_dic[t],i]
            else:
                my_dic[nums[i]] = i

        return []

You can ask me any question if you don't understand the solution

Answer 8

Brute Force (Naive), Time Complexity O(n^2):

class Solution:
    def twoSum(self, nums, target):
        for i in range(0, len(nums)):
            to_find = target-nums[i]
            for j in range(0, len(nums)):
                if j!=i and nums[j] == to_find: 
                    return [i, j]
        return [-1, -1]

Using Sorting, Time Complexity O(nlogn):

class Solution:
    def twoSum(self, nums, target):
        nums = sorted(nums)
        for i in range(len(nums)):
            to_find = target - nums[i]
            left, ryt = 0, len(nums)-1
            while left<ryt:
                mid = (left+ryt)//2
                if mid != i and nums[mid] == to_find:
                    return [i, mid]
                elif nums[mid]>to_find:
                    ryt = mid-1
                else:
                    left = mid+1
        return [-1, -1]

Using Sorting with Two Pointer Approach, Time Complexity O(nlogn):

• Improved version of above sorting approach but still Time Complexity is O(nlogn)

Using Hashmap, Time Complexity O(n):

class Solution:
    def twoSum(self, nums, target):
        num_to_idx = {}

        for i, num in enumerate(nums):
            if target-num in num_to_idx:
                return [i, num_to_idx[target-num]]
            num_to_idx[num] = i
        return [-1, -1]

Answer 9

use hash table is the easiest solution:

class Solution(object):
def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    d = {}
    for i, n in enumerate(nums):
        if n in d:
            return [d[n], i]
        d[target - n] = i

enjoy

Answer 10

Your solution used nested loop which may cause timeout error. You can use dictionary to optimize performance. This is my solution:

class Solution:
    def twoSum(self, num, target):
        map = {}
        for i in range(len(num)):
            if num[i] in map:
                return map[num[i]], i
            else:
                map[target - num[i]] = i
        return -1, -1

What's more, you should never modify public method signature.

Answer 11

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.