[LeetCode] 0001 Two Sum

Two Sum

LeetCode - 0001 Two Sum (Easy)
https://leetcode.com/problems/two-sum/

Problem Description

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

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

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solutions

Brute Force

The easiest way of solving the problem is by using two loops to go through all the numbers in an array, and see if the result matches the target number. However, the time complexity will not be good for this method.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(nums[j] == target - nums[i]){
                    return {i, j};
                }
            }
        }
        return {};  // No two sum solution, return an empty vector
    }
};

• Time complexity is O(n^2) due to two loops
• Space complexity is O(1)

Two-pass Hash Table

In order to improve run time complexity, a more efficient way to check if the complement exists in the array is needed. By using hash map, we are able to do lookup in a constant time.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        std::unordered_map<int, int> lookup;
        for(int i = 0; i < n; i++){
            lookup.insert({nums[i], i});
        }
        for(int i = 0; i < n; i++){
            int diff = target - nums[i];
            if(lookup.count(diff)){
                return {i, lookup[diff]};
            }
        }
        return {};
    }
};

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

One-pass Hash Table

It turns out that we can do it in one-pass. By iterating and inserting elements into the table, we can also look back and check if current element’s complement already exists in the table. If so, we have found the solution and return immediately.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        std::unordered_map<int, int> map;
        for(int i = 0; i < n; i++){
            int diff = target - nums[i];
            if(map.count(diff)){
                return {map[diff], i};
            }
            map[nums[i]] = i;  // same as map.insert({nums[i], i});
        }
        return {};
    }
};

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

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict_map = {}
        for i, n in enumerate(nums):
            if target-n in dict_map:
                return [dict_map[target-n], i]
            else:
                dict_map[n] = i