A More Straightforward Guide to Solving Two Sum.

When approaching the classic two sum problem you can answer in a few different ways. You can attempt a brute method in which you consider every possible number.This would be attempted using a nested for loop. This is not an efficient runtime. Or, you can do the one pass method using a hashmap, which is much more efficient.

Brute Force

Given an array lets use

let array = [2,1, 5, 3]
let target = 4

We are look for 2 numbers in this array to equal the target 4.

2 + 1 = 3
2 + 5 = 7
2 + 3 = 5

After iterating through the array once using the 0th index we can see that 2 is not going to help us reach the target. So we pass through again using the 1st index.

1 + 5 = 6
1 + 3 = 4

Finally, we find two numbers that add up to the target: 1 and 3. In the array, the number 1 is at index 1, and the number 3 is at index 3. Therefore, the answer is [1, 3], indicating that the numbers at indices 1 and 3 of the array sum up to the target value of 4!

Now imagine the array looked like [2, 5, 1, 3] instead. We would have had to iterate through the array 3 times. That is much too much and there is a more efficient method. Enter hashmaps.

What are Hashmaps?

A hashmap is a data structure that stores data in pairs of keys and values. It allows for fast retrieval of values based on their associated keys. That's the textbook definition and a bit confusing so let's try to visualize this.

Imagine you're in a library looking for specific books. Each book has a unique identifier, like a number, known as a 'key.' When you need a particular book, you simply look up its key, and voila, you've found it. This key—whether it's the book title or a number—quickly directs you to the book you're searching for. This method is much faster than searching through every book one by one.

Here's the Plan:

Now that we know what a hashmap is we can use one to solve our problem.

1. Traverse the list once.
2. For each number, calculate its complement(target - current number).
3. Check if this complement exists in our hashmap.
4. If it doesn’t, store the current number with its index.
5. If it does, return the current index and the stored index from the hashmap.

Problem Statement

Given an array of integers and a target integer, your task is to return the indices of two numbers in the array that add up to the target.

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9
Note: you can return the indices in any order and there is only one answer.

Dive into the code?

Not quite. Let's draw this hashmap out!

Hashmap
value: index

Step 1: We start with an empty hashmap and we look at each number and we check something very specific:

• Does the difference between the target and the current number already exist as a key in our hashmap.

Step 2: For the first number(2) the difference between the target (9) and 2 is 7. If we look in the hashmap:

• is 7 noted down already? Of course not, the hashmap is still empty.
• So, write down 2 and where you found it (index 0)

Current Hashmap:

• 2: 0

Step 3: Move to the next number 7 .

• The difference between the target (9) and the number (7) is 2. Is 2 in the hashmap? Yes, and its noted at being at index 0!
• This means you've found the two numbers that add up to the target:2 (from index 0) and 7 (the number you're currently looking at, at index 1).

Updated Hashmap:
2: 0
7: 1

Because you found that both components of the sum are in the hashmap, you can now return their indices: [0, 1]. These indices tell us where in the array each component of the target sum can be found.

Yay!

Let's dive into the code!

Let's remind ourselves or our steps and problem.

Problem

Given an array of integers and a target integer, your task is to return the indices of two numbers in the array that add up to the target.

Steps

1. Traverse the list once.
2. For each number, calculate its complement(target- current number).
3. Check if this complement exists in our hashmap.
4. If it doesn’t, store the current number with its index.
5. If it does, return the current index and the stored index from the hashmap.

If we are going to traverse a list, we should definitely use some sort of loop. I will utilize a for loop to iterate through the array just like I did in the visualization.

The two approaches to solving the 2-sum problem—brute force and the one-pass hashmap method—demonstrate the power of choosing the right data structure for the job. While the brute force method is straightforward, it's not efficient, especially with larger arrays. The hashmap approach, on the other hand, optimizes the process by reducing the number of comparisons needed to find the correct indices. This makes it an ideal choice for real-world applications.

Key Takeaways:

• Efficiency: Using hashmaps can drastically improve the efficiency of your code, reducing the time complexity from O(n²) with brute force to O(n) with hashmaps.

• Simplicity: Despite their power, hashmaps are straightforward to implement and use.

• Practicality: Understanding when and how to use hashmaps is a valuable skill in computer science, applicable to a wide range of problems beyond just the 2-sum issue.

By now, you should have a solid understanding of how the two-sum problem can be efficiently solved using hashmaps! Hope you enjoyed!

Happy Coding!