Skip to content

Two Sum Problem

In this two-sum problem, we use various approaches to solve the problem from brute force to an optimized approach. We also discuss the take-offs and talk about complexity analysis.

Gopi Gorantala
Gopi Gorantala
5 min read

Table of Contents

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

Coding Interview Questions

Gopi Gorantala Twitter

Gopi has been a Full Stack(Java+React) since 2016. He worked in Europe, and India, from startups to tech giants. He has a strong engineering professional with a Bachelor's in Satellite Communications.

Comments


Related Posts

Members Public

Solution Review: Get the First Set Bit Position Using the Right Shift

In the kth bit set/unset problem, we first write the algorithm, then some pseudocode, and then implement the solution.

Members Public

Challenge 1: Get the First Set Bit Position Using the Right Shift

This problem is similar to the last lesson we discussed. If you need a clue, return to the previous lesson to further your understanding.

Members Public

Check If Kth Bit Is Set/Unset Using Right Shift

In the kth bit set/unset problem, we need to write a program that checks whether the kth bit of a number is 1 or 0.