Algorithm Practice: Two Sum

Today we are going to go over how to solve an easy algorithm problem used by many companies for technical interviews called Two Sum.

Problem

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
Input: nums = [3,2,4], target = 6
Output: [1,2]
Input: nums = [3,3], target = 6
Output: [0,1]
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

Solutions

Approach 1: Brute Force

The brute force approach is simple. Loop through each element i and find if there is another value j that when added to i equals to target

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

Approach 2:

Find complementary number and check if it exists in array using indexOf

var twoSum = function(nums, target) {      
for(let i = 0 ; i< nums.length ; i++){
let comp = (target - nums[i])
if (nums.indexOf(comp, i + 1) !== -1){
return [i, nums.indexOf(comp, i + 1)]
}
}
};

Approach 3: Two-pass Hash Table

A better, more efficient way to check if the complement exists in the array, is a hash table. A simple implementation uses two iterations. In the first iteration, we add each element’s value and its index to the table. Then, in the second iteration we check if each element’s complement (target — nums[i]) exists in the table. Beware that the complement must not be nums[i] itself!

var twoSum = function(nums, target) {
if (nums.length === 2) return [0, 1];
const len = nums.length;
let hashTable = {};
for(let i = 0; i < len; i++){
hashTable[nums[i]] = i;
}

for(let i = 0; i < len; i++) {
let complement = target - nums[i];
let found = hashTable[complement];
if(found !== undefined && found != i) return [i, found];
}
return [0,0];
}
  • Space complexity : O(n). The extra space required depends on the number of items stored in the hash table, which stores exactly n elements.

Approach 4: One-pass Hash Table

We can also solve this problem with one pass. We do this by finding if the complement exists in the hash map. if not map the element in the array to its index.

var twoSum = function(nums, target) {
const len = nums.length;
let hashmap = {};
for(let i = 0; i < len; i++) {
let diff = target - nums[i];
let find = hashmap[diff];
if(find !== undefined) return [find, i];
else hashmap[nums[i]] = i;
}
};
  • Space complexity : O(n). The extra space required depends on the number of items stored in the hash table, which stores at most n elements.

Conclusion

We can see that even a simple problem can have a large variety of solutions. For this problem I started out with the simplest of solutions using brute force and addition. A much smarter way would be to find the compliment exists in the array.