Solving the Two Sum Problem in Java: From Brute Force to HashMap Magic

Hello everyone! Today, we’re diving into one of the most common problems asked in FAANG (big tech) interviews: the Two Sum Problem. This problem is also the final project in the easy part of the "Learning Java" series. If you’re preparing for a FAANG interview or just leveling up your Java skills, you’ve got to solve this problem at least once. Let’s break it down step by step, starting with the simplest approach and then moving to a more efficient solution using a HashMap.

What is the Two Sum Problem?

The Two Sum Problem is simple: you’re given an array of integers and a target number. Your task is to find two numbers in the array that add up to the target. For example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] (because 2 + 7 = 9)

Sounds easy, right? But how do we solve it efficiently? Let’s start with the simplest approach and then optimize it.

The Brute-Force Approach

The most straightforward way to solve this problem is to use a brute-force approach. Here’s how it works:

Hold the First Element:
- Take the first element of the array and compare it to every other element in the array.
Compare to Other Elements:
- Check if the sum of the first element and any other element equals the target.
Repeat for All Elements:
- Move to the second element and repeat the process.
- Continue this until you’ve checked all possible pairs.

How to Implement This in Java

To implement this in Java, we’ll use two nested loops:

Outer Loop (Pivot):
- The outer loop will iterate through each element of the array, treating it as the "pivot."
Inner Loop (Comparison):
- The inner loop will iterate through the elements after the pivot.
- For each pair of elements, we’ll check if their sum equals the target.
Return the Indices:
- If a pair is found, we’ll return their indices.
- If no pair is found after checking all combinations, we’ll throw an exception.

Here’s the Java code for the brute-force solution:

public class TwoSumProblem {

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15}; // Example input array
        int target = 9; // Example target

        // Call the brute-force method
        int[] result = bruteForceTwoSum(nums, target);

        // Print the result
        System.out.println("Indices: [" + result[0] + ", " + result[1] + "]");
    }

    public static int[] bruteForceTwoSum(int[] nums, int target) {
        // Outer loop: iterate through each element as the pivot
        for (int i = 0; i < nums.length; i++) {
            // Inner loop: iterate through the elements after the pivot
            for (int j = i + 1; j < nums.length; j++) {
                // Check if the sum of the two elements equals the target
                if (nums[i] + nums[j] == target) {
                    // Return the indices of the two numbers
                    return new int[]{i, j};
                }
            }
        }

        // If no solution is found, throw an exception
        throw new IllegalArgumentException("No two sum solution found.");
    }
}

Why This Works

The brute-force approach checks all possible pairs of numbers in the array. It’s simple and easy to understand, but it’s not efficient for large arrays because it has a time complexity of O(n²).

A More Efficient Solution: Using a HashMap

While the brute-force approach works, it’s not the most efficient way to solve the Two Sum Problem, especially for large arrays. To improve this, we can use a HashMap to solve the problem in O(n) time.

What is a HashMap?

A HashMap is a data structure that stores key-value pairs. It allows you to store and retrieve values in constant time (O(1)) on average. In the context of the Two Sum Problem, we’ll use the HashMap to store numbers from the array as keys and their indices as values.

How the HashMap Solution Works

The idea is to use the HashMap to keep track of the numbers we’ve seen so far and their positions in the array. For each number in the array, we’ll calculate its complement (i.e., the number that, when added to the current number, equals the target). If the complement is already in the HashMap, we’ve found our two numbers!

Here’s the step-by-step process:

Initialize the HashMap:
- Create an empty HashMap to store numbers and their indices.
Iterate Through the Array:
- For each number in the array:
  - Calculate its complement: complement = target - currentNumber.
  - Check if the complement exists in the HashMap.
    - If it does, return the indices of the complement and the current number.
    - If it doesn’t, add the current number and its index to the HashMap.
Handle No Solution:
- If no solution is found after iterating through the array, throw an exception.

Java Code for the HashMap Solution

Here’s the Java code for the HashMap solution:

import java.util.HashMap;
import java.util.Map;

public class TwoSumProblem {

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15}; // Example input array
        int target = 9; // Example target

        // Call the HashMap method
        int[] result = hashMapTwoSum(nums, target);

        // Print the result
        System.out.println("Indices: [" + result[0] + ", " + result[1] + "]");
    }

    public static int[] hashMapTwoSum(int[] nums, int target) {
        // Create a HashMap to store numbers and their indices
        Map<Integer, Integer> map = new HashMap<>();

        // Iterate through the array
        for (int i = 0; i < nums.length; i++) {
            // Calculate the complement
            int complement = target - nums[i];

            // Check if the complement exists in the HashMap
            if (map.containsKey(complement)) {
                // If it exists, return the indices of the two numbers
                return new int[]{map.get(complement), i};
            }

            // Add the current number and its index to the HashMap
            map.put(nums[i], i);
        }

        // If no solution is found, throw an exception
        throw new IllegalArgumentException("No two sum solution found.");
    }
}

Why This Works

The HashMap allows us to check for the complement in constant time (O(1)), making the solution much faster than the brute-force approach.
By storing numbers as keys and their indices as values, we can quickly retrieve the index of the complement when we find it.

Handling Duplicates and Overwriting Indices

One thing to be careful about is duplicate numbers in the array. If you add all elements to the HashMap before checking for complements, you might accidentally overwrite indices and miss valid pairs. For example:

Input: nums = [4, 4, 2, 7, 11, 15], target = 9
If you add all elements to the HashMap first, the second 4 will overwrite the first one, and you might miss the valid pair [2, 3].

To avoid this, we check for the complement before adding the current element to the HashMap. This ensures that we don’t overwrite indices and can still detect valid pairs even if the array contains duplicates.

Conclusion

The Two Sum Problem is a classic interview question that tests your understanding of arrays, loops, and data structures. While the brute-force approach is simple, the HashMap solution is much more efficient and is the preferred method for solving this problem in real-world scenarios.

By mastering both approaches, you’ll be well-prepared for FAANG interviews and similar coding challenges. Happy coding!

Your Turn!

Now it’s your turn to try implementing these solutions. Start with the brute-force approach, then optimize it using a HashMap. Once you’re comfortable, challenge yourself with variations of the problem, such as handling duplicates or finding all possible pairs.

Let me know if you have further questions or need additional clarification! 😊