Two Sum Problem

Introduction

The two Sum problem is a classic problem, and this has been listed first as one of the basic questions one has to solve when prepping for coding interviews. This is one of the most popular questions asked in such interviews.

Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe, and many more top tech companies.

Problem Statement

In the two-sum problem, given an array of integers, nums and an integer, return the indexes 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.

You can return the answer in order.

Test cases

Test case#1:

Input: nums = [2, 7, 11, 15], target = 18

Output: [1, 2] or [2, 1] 
// (because nums[1] + nums[2] == 18, we return [1, 2])

Test case#2:

Input: nums = [3, 2, 4], target = 6

Output: [1, 2] or [2, 1]

Test case#3:

Input: nums = [3, 3], target = 6

Output: [0, 1] or [1, 0]

Sketch

Intuition

There are different ways to solve this problem.

1. Brute force / Maths formula,
2. Hashing (key, value) approach,
3. Two-pass
4. One-pass
5. and with Two pointer technique. (this is for reference)

Brute-force/Naive approach

The brute force approach is simple, looping through each element X and find another value that equals Y. Since X + Y = target.

Solution

import java.util.Arrays;

public class TwoSumBruteForce {
  public static void main(String[] args) {
    int[] input = {2, 7, 11, 15};
    int targetSum = 18;
    System.out.println(Arrays.toString(bruteForce01(input, targetSum)));
  }

  public static int[] bruteForce01(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
      for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] + nums[i] == target) {
          return new int[] {i, j};
        }
      }
    }
    return new int[] {-1, -1};
  }
}

// outputs [1, 2]

or in simple terms, we can say we find X and Y can be replaced with (target - X).

import java.util.Arrays;

public class TwoSumBruteForce {
  public static void main(String[] args) {
    int[] input = {2, 7, 11, 15};
    int targetSum = 18;
    
    System.out.println(Arrays.toString(bruteForce02(input, targetSum)));
  }

  public static int[] bruteForce02(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
      for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] == target - nums[i]) {
          return new int[] {i, j};
        }
      }
    }
    return new int[] {-1, -1};
  }
}

// outputs [1, 2]

Complexity analysis

Time complexity: O(n2), we try to find its complement by looping through the rest of the array, which takes O(n) time. Therefore, the time complexity is O(n2), where n is the length of the elements present in the array.

Space complexity: O(1), as no extra space is utilized.

Memoization/Hashtable approach

Let us consider two variables x and y, so the question asks to find x + y = target.

Let X, Y be the below two numbers. The question clearly states that two numbers add up to the target. We can represent this mathematically by –

   X + Y = 10
=> Y = (10 - X)

So, when iterating the elements, you get X value and check if (10 - X) which is Y is present in the HashTable, isn’t that easy to find? also, this is a constant O(1) lookup time.

Two-pass solution

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

public class TwoSumMemoization {
  public static void main(String[] args) {
    int[] input = {2, 7, 11, 15};
    int targetSum = 18;
    System.out.println(Arrays.toString(twoPass(input, targetSum)));
  }

  public static int[] twoPass(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
      map.put(nums[i], i);
    }

    for (int i = 0; i < nums.length; i++) {
      int complement = target - nums[i];
      if (map.containsKey(complement) && map.get(complement) != i) {
        return new int[] {i, map.get(complement)};
      }
    }

    throw new IllegalArgumentException("No two sum solution");
  }
}

// outputs [1, 2]

Complexity Analysis

Time complexity: O(n), we traverse the list containing n elements exactly twice. Since the hash table reduces the look-up time to O(1), the time complexity is O(n).

Space complexity: O(n), the extra space required depends on the number of items stored in the hash table, which stores n elements.

One-pass solution

The following solution uses HashMap.

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

public class TwoSumMemoization {
  public static void main(String[] args) {
    int[] input = {2, 7, 11, 15};
    int targetSum = 18;
    System.out.println(Arrays.toString(onePass(input, targetSum)));
  }

  public static int[] onePass(int[] nums, int target) {
    HashMap<Integer, Integer> memo = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
      int diff = target - nums[i];

      if (memo.containsKey(diff)) {
        return new int[] {memo.get(diff), i};
      }

      memo.put(nums[i], i);
    }

    return new int[] {-1, -1};
    // throw new IllegalArgumentException("No two sum solution found");
  }
}

// outputs [1, 2]

The following approaches are just for your understanding and don't work for our problem statement. These are just for your practice.

❌  Using HashSet (for practice)

HashSet<> stores elements instead indexes.

import java.util.*;

public class TwoSumMemoization {
  public static void main(String[] args) {
    int[] input = {2, 7, 11, 15};
    int targetSum = 18;
    System.out.println(Arrays.toString(usingHashSet(input, targetSum)));
  }

  public static int[] usingHashSet(int[] nums, int target) {
    Set<Integer> set = new HashSet<>();

    for (int num : nums) {
      int potentialDiff = target - num;
      if (set.contains(potentialDiff)) {
        return new int[]{potentialDiff, num};
      }
      set.add(num);
    }
    return new int[0];
    // throw new IllegalArgumentException("No two sum solution found");
  }
}

Complexity analysis

Time complexity: O(n) is the worst case, where we must iterate all the elements.

Space complexity: O(n) for storing elements in HashTable.

❌ Two-Pointer Approach (for practice)

This approach is just to let you know there is a way to solve it. BUT, since sorting is done to the original array, the array original indexes are disturbed and we won't get the right answer.

This approach comes with a cost, which is sorting the array's elements.

First, sort the array, then use the left and right two-pointer and iterate them over the array.

Solution

import java.util.Arrays;

public class TwoSumTwoPointer {
  public static void main(String[] args) {
    int[] input = {2, 7, 11, 15};
    int target = 18;
    System.out.println(Arrays.toString(twoPointer(input, target)));
  }

  public static int[] twoPointer(int[] nums, int target) {
    Arrays.sort(nums);

    int start = 0;
    int end = nums.length - 1;

    while (start < end) {
      int sum = nums[start] + nums[end];

      if (sum == target) {
        return new int[] {nums[start], nums[end]};
      } else if (sum > target) {
        end -= 1;
      } else {
        start += 1;
      }
    }
    return new int[] {-1, -1};
  }
}

Complexity Analysis

Time complexity: O(NlogN), Sorting takes O(NlogN), and running through a loop takes O(n) time.
So overall, the time complexity is O(NlogN).

Space Complexity: O(1) We didn't flood any data onto memory. We used variables to store temporary data, which is arbitrary.