LeetCode sum two: explanations and solutions with Cpp/Java/Python/Ruby

Challenge Description

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Explanation

Naive solutions

First, we come out with the simplest solution, iterate with array element, check whether there are two value’s sum is target, if true, we get a result, so pseudo code is:

 foreach(v1 in array) {
   foreach(v2 in array){
      if (v2 == target - v1) {
         return (index v1, index v2)
      }
}

Time complexity: $O(N^2)$ Space complexity: $O(1)$

Optimization with hashmap

Time general idea is use space to optimize time complexity. We can use a hashmap to optimize the second loop from O(N) to O(1).

So we build a hashmap, the key is the element of array, and value is the index of the element. This hashmap can be constructed before hand, but a better way is to construct in the same loop of checking.

Time complexity: $O(N)$ Space complexity: $O(N)$

C++

class Solution {
public:

  vector<int> twoSum(vector<int>& arr, int target) {
    map<int, int> m;
    vector<int> result;
    for (int i=0; i < arr.size(); i++) {
      if ( m.find(target - arr[i]) == m.end() ) {
        m[arr[i]] = i; // Note: key is element, value is index
      }else{
        result.push_back(m[target - arr[i]]);
        result.push_back(i);
      }
    }
    return result;
  }

};

Java

Java version is same logic with Cpp version:

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

Python

Why we don’t need a hashmap in Python version, please note the second if test. It’s a pragmatic style for Python check whether a element is in array:

if elment in array: 
   ....

Note we use nums[i+1:] in checking, that means we use part of nums index begin with i+1. According to the document, the time complexity of ‘in’ operator is O(N) for list, so this implementation’s time complexity is: $O(N^2)$

class Solution(object):

    def twoSum(self, nums, target):
        for i in range(0, len(nums)-1):
            if (target - nums[i]) in nums[i+1:]:
                return [nums.index(nums[i]), nums.index((target-nums[i]), i+1)]

Ruby

Ruby’s version is short, the logic is same with a Hashmap.

def two_sum(nums, target)
  hash = {}
  nums.each_with_index do |n, index|
    first = hash[target - n]
    if first != nil && first != index
      return [first, index]
    end
    hash[n] = index
  end
end

Preparing for an interview? Checkout this!