Two Sum Problem: A Complete Guide

Have you ever tried to split a bill with a friend? Imagine you're at a restaurant, and the total bill is $50. You want to pay $20, and your friend will cover the remaining $30. But what if you only had a bunch of smaller bills? You’d need to find two bills that add up to $20. This is very similar to a popular problem in programming called the "Two Sum" problem.

The Two Sum problem is like solving a small puzzle. You’re given a list of numbers, and your goal is to find two numbers that add up to a specific target. It’s a fun challenge that also teaches us a lot about problem-solving and efficiency.

In this blog, we’ll explore the Two Sum problem step by step. We’ll start with a simple approach and then move on to a more efficient solution. By the end, you’ll be able to solve this problem easily and apply the same techniques to other challenges.

Problem statement

You are given an array of integers and a target number. Your task is to find two distinct numbers in the array that add up to the target. You should return the indices of these two numbers.

Sample input

1nums = [2, 7, 11, 15], target = 9

Sample output

1[0, 1]

Explanation:
In this example, the numbers 2 and 7 add up to 9. The indices of these numbers are 0 and 1, so the output is [0, 1].

Understanding the problem

At first, the Two Sum problem might seem simple. But when you start thinking about different ways to solve it, you realize there’s more to it than meets the eye. Imagine trying to find two items in a store that add up to a certain amount of money. You could check every possible pair, but that might take a long time, especially if the store is big. The same is true in programming. We want to find a solution that is not only correct but also efficient.

Brute force approach

The simplest way to solve this problem is to check every possible pair of numbers in the array. For each pair, you add the numbers together and see if they equal the target. If they do, you return the indices of those two numbers. This method is easy to understand but might not be the fastest.

Pseudocode

Let’s break down the solution into simple steps:

• Create an empty hash map (or dictionary).
• Loop through each number in the array.
• For each number, calculate its complement by subtracting the number from the target.
• Check if the complement is in the hash map:
  • If it is, return the indices of the complement and the current number.
  • If it’s not, add the current number and its index to the hash map.
• If no pair is found, return an empty array (or handle it according to the problem requirements).

Python code

1def two_sum_brute_force(nums, target):
2    for i in range(len(nums)):
3        for j in range(i + 1, len(nums)):
4            if nums[i] + nums[j] == target:
5                return [i, j]
6    return []

Explanation

• We use two loops to check every possible pair of numbers.
• If the sum of a pair equals the target, we return their indices.
• If no pair is found, we return an empty list.

Java code

1public class TwoSum {
2    public int[] twoSumBruteForce(int[] nums, int target) {
3        for (int i = 0; i < nums.length; i++) {
4            for (int j = i + 1; j < nums.length; j++) {
5                if (nums[i] + nums[j] == target) {
6                    return new int[] { i, j };
7                }
8            }
9        }
10        return new int[] {};
11    }
12}

C++ code

1#include <vector>
2
3std::vector<int> twoSumBruteForce(const std::vector<int>& nums, int target) {
4    for (int i = 0; i < nums.size(); i++) {
5        for (int j = i + 1; j < nums.size(); j++) {
6            if (nums[i] + nums[j] == target) {
7                return {i, j};
8            }
9        }
10    }
11    return {};
12}

Explanation

• The brute force approach uses nested loops to check every possible pair.
• This method has a time complexity of O(n^2), which can be slow for large arrays.

Smart approach using a hash map

A more efficient way to solve the Two Sum problem is to use a hash map (or dictionary). As you go through the array, you can store each number’s value and its index in the hash map. For each new number, you check if the complement (target minus the current number) is already in the hash map. If it is, you’ve found your two numbers, and you can return their indices immediately.

Python code

1def two_sum(nums, target):
2    num_map = {}
3    for i, num in enumerate(nums):
4        complement = target - num
5        if complement in num_map:
6            return [num_map[complement], i]
7        num_map[num] = i
8    return []

Explanation

• We use a hash map to store each number and its index as we go through the array.
• For each number, we calculate its complement (the difference between the target and the number).
• If the complement is already in the hash map, we return the indices of the two numbers.
• This approach has a time complexity of O(n), making it much faster than the brute force method.

Java code

1import java.util.HashMap;
2import java.util.Map;
3
4public class TwoSum {
5    public int[] twoSum(int[] nums, int target) {
6        Map<Integer, Integer> numMap = new HashMap<>();
7        for (int i = 0; i < nums.length; i++) {
8            int complement = target - nums[i];
9            if (numMap.containsKey(complement)) {
10                return new int[] { numMap.get(complement), i };
11            }
12            numMap.put(nums[i], i);
13        }
14        return new int[] {};
15    }
16}

C++ code

1#include <unordered_map>
2#include <vector>
3
4std::vector<int> twoSum(const std::vector<int>& nums, int target) {
5    std::unordered_map<int, int> num_map;
6    for (int i = 0; i < nums.size(); i++) {
7        int complement = target - nums[i];
8        if (num_map.find(complement) != num_map.end()) {
9            return {num_map[complement], i};
10        }
11        num_map[nums[i]] = i;
12    }
13    return {};
14}

Explanation

• The logic is the same in Python, Java, and C++.
• We use a hash map to track the numbers we’ve seen and their indices.
• This allows us to find the pair in just one pass through the array, making it an efficient solution.

Conclusion

The Two Sum problem is a classic challenge that helps us think about how to solve problems efficiently. While the brute force approach works, it can be slow for large arrays. The hash map method, on the other hand, offers a quick and elegant solution with a time complexity of O(n).

Just like splitting a bill with a friend, solving the Two Sum problem requires careful thought and the right tools. By understanding both the brute force and efficient approaches, you’ll be better prepared to tackle similar problems in the future.