Two Sum solution.

LeetCode problem #1 (Easy): Two Sum

I recently encountered this problem in my first technical interview and I thought it would be helpful to share my solution with you guys! Below will be my naive solution, with the time complexity of O(N^2) and my second solution with O(N) time complexity utilizing the use of the hash table.

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

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

You can return the answer in any order.

Example:

Constraints:

• 2 <= nums.length <= 103
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Initial Thoughts:

• We need to find a pair of numbers that qualify a target Z.
• We can visualize it as A + B = Z.
• We need to keep track of 2 indices at a time: A and (Z-A) indices and compare the values to the target.
• Each input only has 1 possible solution so we don't have to worry about edge cases.

Javascript Naive Solution:

var twoSum = function(nums, target) {
    let result = []

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

Javascript Hash Table Solution:

var twoSum = function(nums, target) {
    let dict = new Object()
    let z = target
    for(let i = 0; i < nums.length; i++){
        let a = nums[i]
        if(!dict[z-a]){
            dict[z-a] = i
        }
    }

    let result = []
    for(let i = 0; i < nums.length; i++){
        if(dict[nums[i]] && i !== dict[nums[i]]) {
            result.push(i, dict[nums[i]])
            return result
        }
    }
};

Explanation:

• First iteration: each time we encounter a value, we would automatically calculate the remaining amount needed in order to reach the target (B and Z-A) and assign it as a key in our dictionary (dict). Its value would be the index of that number itself.
• Second iteration: check if that current value already existed in dict, if it existed and i is different from dict[nums[i]], return that pair of (dict[nums[i]], i).

Example:
nums = [2,7,11,15]
target = 9
Our dictionary would be: { '2': 1, '7': 0, '-2': 2, '-6': 3 }
Output: [ 0, 1 ]