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

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

- Brute force / Maths formula,
- Hashing (key, value) approach,
- Two-pass
- One-pass
- 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^{2}), 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^{2}), 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.

## 👨🏻💻 Gopi Gorantala Newsletter

Join the newsletter to receive the latest updates in your inbox.