LeetCode - Two Sum

Leetcode : Two Sum

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

Input

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

Output

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

Approaches

Approach I - Brute Force

Simply iterate every elements until the sum equals the target.

Solution (C++)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> answer;
        
        for (int i = 0; i < nums.size(); i++)
        {
            for(int j = i + 1; j < nums.size(); j++)
            {
                if (nums[i] + nums[j] == target)
                {
                    answer.push_back(i);
                    answer.push_back(j);
                    
                    return answer;
                }
            }
        }
        return answer;
    }
};

Result

Runtime : 580ms
Memory Usage : 9MB
Runtime Beats 24.96% of C++ Submission

Approach II - Use Unordered Map / Dict

Create an unordered map to save the value and the index. And compare the values in the map with the value - match. (match = target - nums[i])

Solution (C++)

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

Solution (Python)

class Solution(object):
    def twoSum(self, nums, target):
        prev = {}
    
        for i, j in enumerate(nums):
            match = target - j

            if match in prev:
                return [prev[match], i]
            else:
                prev[j] = i
        

Solution (JS)

let twoSum = function(nums, target) {
    let result = []; 
    
    for(let i = 0; i < nums.length; i++) {
        for(let j = i + 1; j < nums.length; j++) {
            if(nums[i] + nums[j] === target) {
                result.push(i, j)
            }
        }
    }
    
    return result; 
};

Result

Runtime : 12ms
Memory Usage : 10.1MB
Runtime Beats 97.10% of C++ Submission