Two Sum problem, 4 different ways to solve it

Two Sum problem
Two Sum problem

Overview

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. Leetcode, one of the largest tech communities with hundreds of thousands of active users to participate and solve coding problems, listed this as the first problem in their curriculum – the Leetcode TwoSum Problem.

Let us discuss the Two Sum algorithm of a given input. This is one of the most popular questions asked in coding 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 TwoSum problem, given an array of integers, nums and an integer, return 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.

Example 01:

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

Output: [2, 7] // (because nums[0] + nums[1] == 9, we return [2, 7])

Example 02:

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

Output: [2, 4]

Example 03:

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

Output: [3, 3]

Thought Process

First Way

Let us consider the array as {3, 5, -4, 8, 11, 1, -1, 6}, and target = 10.

Considering unique integers, you can use the Set interface or Map in Java.

Let X, Y below the 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 present in the HashTable, isn’t that easy to find? also, this is a constant lookup time.

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

Space complexity is O(n), storing elements is HashTable.

Second way:

Any optimizations to the above?

Can we solve this in a more optimal with no extra space?

Yes, first, we sort the entire array, and then we use the two pointers left, right to find the target sum.

  1. Sorting takes O(NlogN) and finding the sum takes O(n).
  2. Overall the time it takes is O(NlogN) and space O(1).
    We look at this two-pointer approach. At last, let us see some of the options we can solve this.
Important Note: We recommend you run through all the solutions shown here. Don’t jump to the optimal solutions directly as they might help you but won’t improve your thought process at real coding interviews.

If you want to get good with algorithms and problem-solving and improve your understanding of problems and ways to handle them, then you need to see how solutions are implemented in all possible ways.

Solution

Approach 1: Brute Force

The brute force approach is simple, loop through each element x and find another value that equals (target - x).

import java.util.Arrays;

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

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

Complexity Analysis

Time complexity: O(n2), for each element, 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.

Approach 2: Two-Pass HashTable

We need a more efficient way to check if the complement exists in the array to improve our run time complexity.

If the complement exists, we need to look up its index. What is the best way to maintain a mapping of each element in the array to its index?

We reduce the lookup time from O(n) to O(1) by trading space for speed. A hash table is built exactly for this purpose. It supports fast lookup in the next constant time.

I say “near” because a look-up could degenerate to O(n) time if a collision occurred. But look up in hash table should be amortized O(1) time as long as the hash function was chosen carefully.

A simple implementation uses two iterations. We add each element’s value and index to the table in the first iteration.

Then, in the second iteration, we check if each element’s complement(target - nums[i]) exists in the table. Beware that the complement must not be nums[i] itself!

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

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

  public static int[] twoSum(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");
  }
}

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.

Approach 3: One-Pass HashTable

It turns out we can do it in one pass. While we iterate and insert elements into the table, we also check if the current element’s complement already exists in the table. If it exists, we have found a solution and returned it immediately.

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

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

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

    for (int i = 0; i < nums.length; i++) {
      int potentialDifference = target - nums[i];
      if (map.containsKey(potentialDifference)) {
        return new int[]{map.get(potentialDifference), i};
      }
      map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
  }
}

So, let’s see how we can achieve the same using the Set interface.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

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

  public static int[] twoSum(int[] array, int targetSum) {
    Set<Integer> set = new HashSet<>();

    for (int num : array) {
      int potentialDiff = targetSum - num;
      if (set.contains(potentialDiff)) {
        return new int[]{potentialDiff, num};
      }
      set.add(num);
    }
    // Write your code here.
    return new int[0];
  }
}

Complexity Analysis

Time complexity: O(n) We traverse the list containing n elements only. Each lookup in the table only costs O(1) time.

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

Approach 4: Two Pointer

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

import java.util.Arrays;

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

  public static int[] twoSum(int[] array, int targetSum) {
    Arrays.sort(array);

    int left = 0;
    int right = array.length - 1;

    while (left <= right) {
      int s = array[left] + array[right];

      if (s == targetSum) {
        return new int[]{array[left], array[right]};
      } else if (s < targetSum) {
        left++;
      } else if (s > targetSum) {
        right--;
      }
    }
    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.


Extras

If you are interested in mastering bit tricks, I've got a course that is loved by more than 100k+ programmers.

In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can optimize your algorithmic and problem-solving skills. The course has simple explanations with sketches, detailed step-by-step drawings, and various ways to solve it using bitwise operators.

These bit-tricks could help in competitive programming and coding interviews in running algorithms, mostly in O(1) time.

This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG(Facebook, Amazon, Apple, Netflix, and Google) companies.

To kick things off, you’ll start by learning about the number system and how it’s represented. Then you’ll learn about the six bitwise operators: AND, OR, NOT, XOR, and bit shifting. You will get tons of hands-on experience working through practice problems to help sharpen your understanding.

By completing this course, you will be able to solve problems faster with greater efficiency!! 🤩

Link to my course: Master Bit Manipulation for Coding Interviews.