The Two Sum problem is a well-known coding challenge frequently encountered in technical interviews. It tests your ability to efficiently search for pairs in an array that sum up to a target value. This post will guide you through solving the Two Sum problem in Java, covering both a brute-force approach and an optimized solution using a hashmap. By the end, you’ll have a clear understanding of how to implement an efficient solution.

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to the target.

Constraints:

  1. You may assume that there is exactly one solution.
  2. You cannot use the same element twice.

Example:

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

Step-by-Step Solution

Step 1: Brute-Force Approach

The simplest approach is to use a nested loop to check all possible pairs of numbers and see if their sum equals the target. While this works, it is inefficient for large arrays due to its quadratic time complexity.

Approach:

  1. Iterate through each element in the array.
  2. For each element, check if any of the following elements add up to the target.
  3. If a valid pair is found, return their indices.

Java Code (Brute Force):

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] {i, j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

Explanation:

  • The outer loop iterates through each number in the array.
  • The inner loop checks the subsequent numbers to see if their sum equals the target.
  • If a valid pair is found, their indices are returned.

Time Complexity:

  • Time Complexity: O(n^2) — Each number is compared with every other number in the array, resulting in a quadratic time complexity.

Example:

public class Main {
    public static void main(String[] args) {
        TwoSum ts = new TwoSum();
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = ts.twoSum(nums, target);
        System.out.println("Indices: " + result[0] + ", " + result[1]);  // Output: Indices: 0, 1
    }
}

Step 2: Optimized Approach Using a HashMap

The brute-force solution works but is inefficient for large datasets. To improve it, we can use a HashMap to store numbers we've seen and their indices. This way, we can solve the problem in linear time.

Optimized Approach:

  1. Initialize an empty HashMap to store the numbers and their indices.
  2. Iterate through the array.
  3. For each element, calculate the difference between the target and the current element.
  4. Check if this difference exists in the HashMap.
    • If it does, return the current index and the index from the HashMap.
    • If it doesn’t, store the current number and its index in the HashMap for future reference.

Java Code (Optimized Solution):

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

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] {map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        
        throw new IllegalArgumentException("No two sum solution");
    }
}

Explanation:

  • Map<Integer, Integer> map: This HashMap stores numbers as keys and their indices as values.
  • For each number in the array, calculate the complement (target - nums[i]).
  • If the complement already exists in the map, the solution is found, and the indices are returned.
  • If not, store the current number and its index in the map and continue.

Time Complexity:

  • Time Complexity: O(n) — We iterate through the array once, and each lookup in the HashMap takes constant time.

Example:

public class Main {
    public static void main(String[] args) {
        TwoSum ts = new TwoSum();
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = ts.twoSum(nums, target);
        System.out.println("Indices: " + result[0] + ", " + result[1]);  // Output: Indices: 0, 1
    }
}

In this example, when the iteration reaches 7, it computes 9 - 7 = 2. Since 2 is already in the map (with index 0), it returns [0, 1].

Edge Cases

While the problem guarantees exactly one solution, you should still account for various edge cases during implementation:

  1. Negative and Positive Numbers:
    The array may contain both negative and positive numbers. Ensure that the solution works for both.

    int[] nums = {-3, 4, 3, 90};
int target = 0;
int[] result = twoSum(nums, target);
System.out.println(result[0] + ", " + result[1]);  // Output: 0, 2

  2. Duplicate Values:
    The array may contain duplicate values, and the solution should still return the correct indices.

    int[] nums = {3, 3};
int target = 6;
int[] result = twoSum(nums, target);
System.out.println(result[0] + ", " + result[1]);  // Output: 0, 1

  3. Array with Only Two Elements:
    Since the problem guarantees at least two elements, the array can have exactly two elements, and the solution should still work.

    int[] nums = {1, 4};
int target = 5;
int[] result = twoSum(nums, target);
System.out.println(result[0] + ", " + result[1]);  // Output: 0, 1

  4. Zeros in the Array:
    If the array contains zeros, the solution should correctly handle the target involving zero.

    int[] nums = {0, 4, 3, 0};
int target = 0;
int[] result = twoSum(nums, target);
System.out.println(result[0] + ", " + result[1]);  // Output: 0, 3

  5. Large Inputs:
    If the array contains a large number of elements, the hash map approach ensures efficiency even with significant data size.

    int[] nums = new int[100000];
for (int i = 0; i < 100000; i++) {
    nums[i] = i;
}
int target = 199999;
int[] result = twoSum(nums, target);
System.out.println(result[0] + ", " + result[1]);  // Output: 99998, 99999

Conclusion

The Two Sum problem is a great exercise to learn about the trade-offs between brute-force and optimized solutions. By using a HashMap in Java, we were able to reduce the time complexity from O(n^2) to O(n), making the solution scalable for larger arrays.

Mastering this problem will not only help you improve your problem-solving skills but also give you a better understanding of efficient data structures like HashMaps, which are invaluable in many algorithmic challenges.