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. 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

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]

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, loop through each element X and find another value that equals Y. Since X + Y = target.

Solution

Java

class Solution {
    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[j] + nums[i] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }
}

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

class Solution {
    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[j] == targetSum - nums[i]) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }
}

JavaScript

var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
      for (let j = i + 1; j < nums.length; j++) {
        if (nums[j] + nums[i] == target) {
          return [i, j];
        }
      }
    }
    return [-1, -1];
};

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

var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
      for (let j = i + 1; j < nums.length; j++) {
        if (nums[j] == targetSum - nums[i]) {
          return [i, j];
        }
      }
    }
    return [-1, -1];
};

TypeScript

function twoSum(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[j] + nums[i] == target) {
                return [i, j];
            }
        }
    }
    return [-1, -1];
}

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

function twoSum(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[j] == targetSum - nums[i]) {
                return [i, j];
            }
        }
    }
    return [-1, -1];
}

Complexity analysis

Time complexity:

O(n²), 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(n²), 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 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 is present in the HashTable, isn’t that easy to find? also, this is a constant O(1) lookup time.

Two-pass solution

Java

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.

One-pass Solution

Java

Using HashMap =>

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

This can also be done with HashSet for Java Langauge.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        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);
        }
        return new int[0];
        // throw new IllegalArgumentException("No two sum solution found");
    }
}

JavaScript

var twoSum = function(nums, target) {
  const memo = {};

  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];
    if (diff in memo) {
      return [memo[diff], i];
    } else {
      memo[nums[i]] = i;
    }
  }
  return [-1, -1];
};

TypeScript

function twoSum(nums: number[], target: number): number[] {
    const memo = {};

    for (let i = 0; i < nums.length; i++) {
        const diff = target - nums[i];
        if (diff in memo) {
            return [memo[diff], i];
        } else {
            memo[nums[i]] = i;
        }
    }
    return [-1, -1];
}

console.log(twoSum([2, 7, 11, 15], 9));

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.

❌ 3. Two Pointer Approach

Note: I want you to know that 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.

Solutions

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Arrays.sort(nums);

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

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

                if (s == target) {
                    return new int[]{nums[left], nums[right]};
                } else if (s < target) {
                    right--;
                } else if (s > target) {
                    left++
                }  
        }
        return new int[]{-1, -1};
    }
}

JavaScript

function twoSum(nums, target) {
    nums.sort();

    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        let s = nums[left] + nums[right];

        if (s === target) {
            return [nums[left], nums[right]];
        } else if (s < target) {
            right--;
        } else if (s > target) {
            left++;
        }
    }
    return [-1, -1];
}

console.log(twoSum([2, 7, 11, 15], 9));

TypeScript

function twoSum(nums: number[], target: number): number[] {
    nums.sort();

    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        let s = nums[left] + nums[right];

        if (s === target) {
            return [nums[left], nums[right]];
        } else if (s < target) {
            right--;
        } else if (s > target) {
            left++;
        }
    }
    return [-1, -1];
}

console.log(twoSum([2, 7, 11, 15], 9));

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.