Two Sum

Why?

This is the re(start) of my leetcode journey. I will admit that I am a bit rusty with leetcode questions as I have been more focused on applications and implementations with my work and did not see much need for it. Regardless, leetcode is an industry standard testing tool and it is probably best to keep this skill warm.

I will be working through Grind75 list of leetcode questions as it holds the most commonly asked questions in interviews. I want to try to be as efficient as I could when it comes to ‘grinding’ leetcode as, over time I’ve noticed that this becomes more of a “memorizing the algorithm & pattern” rather than actually building something useful.

Leetcode link: https://leetcode.com/problems/two-sum/description/

Problem: Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to 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 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: 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 <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Only one valid answer exists.

Thought process + Solution

As with most problems, starting with a brute force approach is probably a decent start as it helps us find areas that needs optimizing. The straight-forward brute force approach would be to

Brute Force

1. Loop through the list
2. Add current number to every number that is ahead of it one at a time (or you could also check whether the number ahead is target-current)
3. Check if it is target
4. Repeat with the next number

Here’s an example

For target = 26, nums = [2,7,11,15]

First iteration: try 2+7, 2+11, 2+15 - None of these add up to 26

Second iteration: try 7+11, 7+15 - None of these also add up to 26

Third iteration: try 11+15 - This adds up to 26

This approach is an O(n^2) approach which is quite slow. It is O(n^2) because we have to essentially loop through the list n number of times.

It looks like what’s slowing down our algorithm is the amount of times we have to loop through the list to see if there is a number that when added to the current number, equates to the target. Lookup time seems to be our problem here. An array has a lookup time of O(n) as to check if a value exists in the array, we'd have to go through the entire list hence O(n). A HashMap on the other hand, has a lookup time of O(1) , why is that?

The way a HashMap works is, you’ve guessed it, by hashing the values. Instead of checking the entire list again and again to see if a value exist, we apply a hashing algorithm to our value which gives it an index. Now, we can find if result - current exists in O(1) time.

Efficient implementation

Here is my solution

var twoSum = function(nums, target) {

		// Make a new hashmap
    hash = new Map()
		
		// Loop through the number list
    for (let i = 0; i < nums.length; i++) {
        // if hashmap contains the complement, i.e. target - current value,
        // get that value's index and return it with current index
        if (hash.has(target-nums[i])) {
            const val = hash.get(target-nums[i])
            return [i, val]
        }
				
				
				// else store the current value + it's index
        hash.set(nums[i], i)
        
    }
 
};

This solution is an O(n) solution, Why?

1. We loop through the list of numbers which takes O(n)
2. Insertion and lookup operations on HashMap is both O(1) , essentially constant time
3. Since there are other time complexities(in this case linear time O(n), we can omit the O(1) constant time

Hence overall time complexity is O(n) .

Do note that in this solution, we are trading space for speed, in our case we made a new hash map which adds O(n) worst case to our space complexity.

A Thank You

Thank you for taking the time to read this blog, if you notice any issues or inaccuracies with this blog please feel free to contact me at limoudom2001@gmail.com.

Thank you once again, Merry Christmas and have a wonderful new year 🥳.