Two Sum solution.

#beginners #algorithms #javascript

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:

Example 1:
Input	nums = [2,7,11,15], target = 9
Output	[0,1]
Expanation	Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:
Input	nums = [3,2,4], target = 6
Output	[1,2]

Example 3:
Input	nums = [3,3], target = 6
Output	[0,1]

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 ]

How I fixed 20 seconds of lag for every user in just 20 minutes.

Our AI agent was running 10-20 seconds slower than it should, impacting both our own developers and our early adopters. See how I used Sentry Profiling to fix it in record time.