Skip to content

Two Sum Problem (Solutions in Java, JS, and TS)

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

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 QuestionsArraysJavaScript

Gopi Gorantala Twitter

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Comments


Related Posts

Members Public

Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Leetcode 217: Contains Duplicate
Members Public

Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. 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,

Leetcode 121: Best Time To Buy and Sell Stock
Members Public

Arrays From Zero To Mastery: A Complete Notes For Programmers

This article discusses array data structure with sketches, memory diagrams, array capacity vs. length, strengths & weaknesses, big-O complexities, and more!