Two Sum Problem Using Hash Tables

Have you ever needed to find two specific items in a list that add up to a certain value? This is the core idea behind the “Two Sum” problem, a classic puzzle in the world of programming. It’s often used in interviews because it tests your understanding of basic algorithms and data structures. While there are simple ways to solve it, using a hash table makes the solution remarkably fast and efficient. Let’s dive in and see how!

What is the Two Sum Problem?

Imagine you have a list of numbers and a target number. Your goal is to find two numbers within that list which, when added together, equal the target number. If you find such a pair, you usually need to return their positions (indices) in the original list.

Example:

  • List of numbers: [2, 7, 11, 15]
  • Target sum: 9

In this list, the numbers 2 and 7 add up to 9. If 2 is at index 0 and 7 is at index 1, the answer would be [0, 1].

A Simple (but Slow) Approach

The most straightforward way to solve this is to check every possible pair of numbers in the list.

  1. Take the first number.
  2. Add it to the second number. Does it equal the target?
  3. If not, add the first number to the third number. Does it equal the target?
  4. Continue this until you’ve paired the first number with every other number.
  5. If you haven’t found a pair, repeat the process starting with the second number, pairing it with the third, fourth, and so on.
  6. Keep going until you find a pair that sums to the target or you run out of pairs to check.

This method works, but it can be slow, especially for long lists. You have to compare almost every number with every other number. This approach has a time complexity of O(n^2), where n is the number of items in the list. For large lists, this can take a significant amount of time.

The Efficient Solution: Using Hash Tables

Hash tables offer a much faster way! Remember that hash tables are incredibly good at quickly checking if an item exists within them (an operation that takes O(1) time on average). We can use this superpower to solve the Two Sum problem efficiently.

Here’s the idea:

  1. Go through the list of numbers one by one.
  2. For each number (num), calculate the complement needed to reach the target (complement = target - num).
  3. Instead of searching the rest of the list for this complement (which is slow), quickly check if the complement is already stored in our hash table.
  4. If the complement is in the hash table: Hooray! We’ve found our pair. The current number (num) and the complement stored in the hash table add up to the target. We can return their indices.
  5. If the complement is NOT in the hash table: Store the current number (num) and its index in the hash table. Then, move on to the next number in the list.

Why does this work? As we iterate through the list, we store the numbers we’ve already seen in the hash table. When we look at a new number, we can instantly check if the number needed to complete the pair (the complement) has been seen before.

Tip

Think of it like looking for a matching sock. Instead of dumping all socks on the floor and comparing every sock with every other sock (the O(n^2) approach), you pick up one sock and check a drawer (the hash table) where you’ve already placed its potential match. If the match is in the drawer, you’re done! If not, you place the current sock in the drawer and pick up the next one.

Step-by-Step Walkthrough

Let’s use our example again: nums = [2, 7, 11, 15] and target = 9. We’ll use a hash table (let’s call it seen_numbers) to store numbers and their indices.

  1. Start: seen_numbers is empty {}.
  2. Look at 2 (index 0):
    • Calculate complement: 9 - 2 = 7.
    • Is 7 in seen_numbers? No.
    • Add 2 and its index 0 to seen_numbers: {2: 0}.
  3. Look at 7 (index 1):
    • Calculate complement: 9 - 7 = 2.
    • Is 2 in seen_numbers? Yes! It’s associated with index 0.
    • We found the pair! The current number 7 (at index 1) and the complement 2 (at index 0) add up to 9.
    • Return the indices: [0, 1]. We are done!

Notice how we only had to go through the list once.

Here’s a simple representation in pseudo-code:

function findTwoSum(nums, target):
  seen_numbers = empty hash table // e.g., {}

  for index from 0 to length(nums) - 1:
    current_num = nums[index]
    complement = target - current_num

    if complement is in seen_numbers:
      complement_index = seen_numbers[complement]
      return [complement_index, index] // Found the pair!

    // If complement not found, add current number and index to hash table
    seen_numbers[current_num] = index

  // If the loop finishes without finding a pair
  return [] // Or indicate no solution found

This hash table approach significantly speeds up the process.

  • Time Complexity: We only iterate through the list once. Each lookup and insertion in the hash table takes O(1) time on average. So, the total time complexity is O(n). Much better than O(n^2)!
  • Space Complexity: In the worst case, we might store almost all the numbers from the list in the hash table before finding the pair. Therefore, the space complexity is O(n) because we need extra space proportional to the number of elements in the input list.

Conclusion

The Two Sum problem is a great example demonstrating the power and efficiency of hash tables. By using a hash table to store numbers we’ve already encountered, we can quickly check for the needed complement, reducing the search time dramatically from O(n^2) to O(n). This technique of trading a bit of extra memory (for the hash table) for a significant speedup is very common and useful in programming.

What’s Next?

Now that you’ve seen how hash tables can efficiently solve the Two Sum problem, you might be interested in exploring other ways hash tables are used:

Exploring these topics will solidify your understanding of hash tables and show you more ways this powerful data structure can be applied to solve common programming challenges.