Two Sum Problem

Cracking the Two Sum Problem: Brute Force, HashMap, and Sorting Approaches

The Two Sum problem is a classic coding interview question: Given an array of integers nums and a target integer target, find the indices of the two numbers in nums that add up to target. Each input is guaranteed to have exactly one solution, and you can't use the same element twice.

Let's explore three common approaches: brute force, HashMap, and sorting, highlighting their pros and cons.

1. Brute Force (O(n^2) Time, O(1) Space)

The brute-force method uses nested loops to check every possible pair of numbers.

Java

public int[] twoSumBruteForce(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};
            }
        }
    }
    return new int[0]; // No solution (problem constraint says there will be one)
}

• Advantage: Simple to understand and implement.

• Disadvantage: Inefficient for large datasets due to its quadratic time complexity.

2. HashMap (O(n) Time, O(n) Space)

The HashMap approach stores each number and its index in a HashMap. For each number, we check if its complement (target - number) is already in the map.

Java

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

public int[] twoSumHashMap(int[] nums, int target) {
    Map<Integer, Integer> numMap = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (numMap.containsKey(complement)) {
            return new int[] {numMap.get(complement), i};
        }
        numMap.put(nums[i], i);
    }
    return new int[0]; // No solution
}

• Advantage: Very efficient with linear time complexity.

• Disadvantage: Uses extra space to store the HashMap.

3. Sorting (O(n log n) Time, O(n) Space)

This method first sorts the array and then uses two pointers (left and right) to find the two numbers. We need to store the original indices, so we clone the array before sorting.

Java

import java.util.Arrays;

public int[] twoSumSorting(int[] nums, int target) {
    int[] sortedNums = nums.clone();
    Arrays.sort(sortedNums);
    int left = 0;
    int right = sortedNums.length - 1;

    while (left < right) {
        int sum = sortedNums[left] + sortedNums[right];
        if (sum == target) {
            int[] indices = new int[2];
            //Find original indices
            boolean foundLeft = false;
            boolean foundRight = false;
            for(int i=0; i<nums.length; i++){
                if(nums[i] == sortedNums[left] && !foundLeft){
                    indices[0] = i;
                    foundLeft = true;
                }
                if(nums[i] == sortedNums[right] && !foundRight){
                    indices[1] = i;
                    foundRight = true;
                }
                if(foundLeft && foundRight) break;
            }
            return indices;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[0]; // No solution
}

• Advantage: Can be useful if memory is a significant constraint (though HashMap is generally better).

• Disadvantage: Slower than the HashMap approach due to the sorting step.

Which Approach is Best?

For most cases, the HashMap approach is the most efficient and preferred solution due to its O(n) time complexity. It offers a good balance between speed and memory usage. The sorting approach can be considered if you have strict memory limitations, but it is less efficient. Avoid the brute-force approach for anything but the smallest datasets.