Solving “Two Sum” Coding Interview Problem Efficiently

Problem Statement:

Given an array of integers, nums, and an integer target, return the indices of the two numbers such that they add up to the target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

For the array nums = [2, 7, 11, 15] and target = 9, the answer would be [0, 1] because nums[0] + nums[1] = 2 + 7 = 9.

Brute Force Solution:

For each number, check all other numbers to see if they add up to the target.

public class TwoSumSolution {
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSumBruteForce(nums, target);
        System.out.println(Arrays.toString(result)); // Output should be [0, 1]
    }

    public static 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};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

This solution has a time complexity of O(n²) due to the nested loops.

Optimal Solution:

Imagine you’re shopping and you have a certain amount of money to spend (this is our target). For every item you consider buying (each number in our nums array), you think: “How much more do I need to spend to reach my budget?” This “needed amount” is the essence of solving the Two Sum problem.

Use a hashmap (or dictionary in some languages) to keep track of numbers you’ve seen so far and their indices. This allows you to determine in constant time whether a complement for the current number (i.e., target - nums[i]) exists. Complement value is the needed amount you need to check for each number as you iterate over the array.

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

public class TwoSumSolution {

    public static int[] twoSumOptimal(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);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

This solution has a linear time complexity of O(n), making it much more efficient as the array size grows.

By using a hashmap, we’re creating a fast-access record of all numbers we’ve previously seen. This means that for every new number, we only need to check if its required complement to reach the target is in the record, rather than re-examining every other number in the array.