Two Sum, Zero Headaches

Solve This Technical Interview Question With Ease And Learn The Power Of The HashMap

Photo by Sereja Ris on Unsplash

I’m sure we’ve all felt this small when starting to learn new technologies. When I first started my journey into the depths of more complex coding challenges, I saw the need for one thing — a greater understanding of how various data structures can be manipulated. My first programming language was JavaScript so that is where my quest to learn these new ideas began. Some mental blockers for me, and probably many others, were understanding how to navigate through the data structure, how data structures can store other complex data structures, and how manipulating data in data structures can be more complicated than it first appears. After a while, I became more and more comfortable working with various data structures and learning new ways to store and utilize the data I needed.

Of course, as I was preparing to tackle real-life interviews, I took to LeetCode to learn. One of the first problems I tackled to help reinforce my skills was the LeetCode problem of Two Sum. I’m sure like many others this was no small feat, however, after pushing through I eventually came up with a solution. Looking back, I know now it wasn’t the DRYest code or the most efficient, but I was proud because I wrote it myself and it worked! Little did I know, this problem would come back into my world only a short time later.

Once I began to learn Java, I knew the importance of learning data structures as they are the building blocks of how data is stored and organized regardless of the programming language used. This is when I went back to LeetCode and tried my new skills on the Two Sum problem once again. Today I will be breaking down the use of the Java HashMap to help solve this common problem.

Photo by Jarek Ceborski on Unsplash

The HashMap in Java is a class that can be used to insert, delete, and locate items in a map. That, of course, is a simple technical explanation, but what if you wanted to explain that to a friend? Think of it like organizing utensils in your kitchen. You may have a single drawer (a HashMap) and inside that drawer, you may have spoons, forks, and knives (these would be the keys in this map). But what if you wanted to host a party? What good does it do just knowing you have those items — you also need to know the quantity of those items. This is where the key-value pair association comes in handy. So you have your drawer (your HashMap), and you have 10 (the value) spoons (the key), 10 (the value) forks (the key), and 10 (the value) knives (the key). Perfect for having a party!

If we put this information into a HashMap in Java this is a rough idea of what we might see when we print out that info:

utensilDrawer = {
      "spoons" = 10,
      "forks" = 10,
      "knives" = 10
}

As you can see it is a nicely organized way to store data that can be used later.

Now let's get to our problem:

The Two Sum problem is a problem where we are provided a list of integers and a target integer. We need to use this list of integers to find two numbers whose sum is equal to the target integer. In this problem, the expected return is the indices, or where the integers occur in the list, of the two summed integers. The two indices should be in a list.

Example:

Input: list = [1,2,5,7,9], target = 9
Output: [1,3]

In this case, we can see that the integers 2 and 7 can be summed to equal 9. Since lists are zero-indexed, 2 is at index 1 and 7 is at index 3.

One way we can accomplish this goal is to look at each integer in the list, add it to every other integer, and compare the sum to the target.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Intitalize a new list we will return to our result
        int[] result = new int[2];
        
        // Loop through the array checking each integer against the others.
        for(int i = 0; i < nums.length; i++){
            for(int j = i+1; j < nums.length; j++){
                // Once we have found two integers that sum to equal the target
                // add those integers to the result array and return.
                if(nums[i] + nums[j] == target){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return result;
    }
}

While this solution works, it relies on nested loops, which is not very efficient and at larger input list sizes would cause a slowdown in our program.

To combat this inefficiency we will employ the HashMap:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        HashMap<Integer, Integer> sumOfNums = new HashMap();

        for(int i = 0; i < nums.length; i++){
            if(sumOfNums.containsKey(nums[i])){
                return new int[] {sumOfNums.get(nums[i]), i};
            }
            else {
                sumOfNums.put(target-nums[i], i);
            }
        }
        return null;
    }
}

At the start of each iteration of the loop, we are checking to see if we have found the integer pair of the current integer. This is seen here:

if(sumOfNums.containsKey(nums[i])){
    return new int[] {sumOfNums.get(nums[i]), i};
}

We check our HashMap using the containsKey() method that is built into the HashMap class to check if we have seen the integer pair where the current integer and the sum of the pair would equal the target. If the key is present, the boolean true is returned into the if statement by the containsKey() method, and we then return the value of that key using the get() method and the current index, i, into a new list.

In the case of the containsKey() method returning a boolean false, the HashMap is used to store the integer we are looking for that will be the correct sum of the integer at the index stored in the key. We can visualize this on this line:

sumOfNums.put(target-nums[i], i);

We take our current integer at nums[i] and subtract it from the target, leaving us the integer that would make the correct sum and store it as the key. Then we store the index of the current num as the value.

Let’s see what it would look like at each iteration of the loop

Input: list = [1,2,5,7,9], target = 9

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        HashMap<Integer, Integer> sumOfNums = new HashMap();

        for(int i = 0; i < nums.length; i++){
            if(sumOfNums.containsKey(nums[i])){
                return new int[] {sumOfNums.get(nums[i]), i};
            }
            else {
                sumOfNums.put(target-nums[i], i);
            }
        }
        return null;
    }
}

twoSum([1,2,5,7,9], 9)
// First iteration HM = {8=0}
// Second iteration HM = {8=0, 7=1}
// Third iteration HM = {8=0, 7=1, 4=2}
// Fourth iteration we see the key 7 in our HM where the key-value pair
// is equal to 7=1, so we return the key and our current index

To break down the code and visualize each loop:

1. The first iteration of the loop runs and we can see the if statement would look like this: sumOfNums.containsKey(1)
2. This return false since there is nothing in our HashMap, so the else statement would execute and store: sumOfNums(9–1, 0) -> The key-value pair 8=0 is stored.
3. The second iteration of the loop runs, and we can see that key of 2 is not in our HashMap, so we then store the key-value pair 7=1 (9–2) in our HM.
4. The third iteration: Again, no key of 5 is in the HashMap, so we store the key-value pair 4=2 (9–5) in the HashMap.
5. On this next and last iteration, the if statement sumOfNums.containsKey(7) which is true as the key of 7 was stored from a previous iteration. We will then get the value for the key 7 which is 1, and return it along with the current index, 3, as an array literal visualized like this: new int[] {sumOfNums.get(nums[i]), i};

While this may seem like a lot of work, it is significantly more efficient, especially as the size of the input grows.

Learning more about data structures and how they can be implemented in our code can be daunting. With some patience and a lot of practice, finding new techniques to use different data structures is quite fun and makes our lives as programmers easier. I encourage everyone to think about the use cases for the various data structures as they are very powerful tools when building new applications and solving complex problems.