Hello coders! Today we will be discussing the various solutions to the Two Sum LeetCode Problem.

## Problem Statement

Given an array of integersĀ `nums`

Ā and an integerĀ `target`

, returnĀ *indices of the two numbers such that they add up toĀ ** 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 any order.

**Example 1:**

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

**Output:** [0,1]

**Explanation:** Because nums[0] + nums[1] == 9, we return [0, 1].

**Example 2:**

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

**Output:** [1,2]

**Example 3:**

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

**Output:** [0,1]

**Constraints:**

`2 <= nums.length <= 10`

^{4}`-10`

^{9}`Ā <= nums[i] <= 10`

^{9}`-10`

^{9}`<= target <= 10`

^{9}**Only one valid answer exists.**

## Approach 1: Brute Force

In this problem we're trying to find two numbers from the given array that add up to a target - so why don't we try all possible solutions by adding every number in the array to all the other numbers?

This clearly won't be the most optimal approach, but at least it is a working solution.

### Implementation

```
1public int[] twoSum(int[] nums, int target) {
2 if (nums == null) {
3 return new int[]{-1, -1};
4 }
5 for (int i = 0; i < nums.length - 1; i++) {
6 for (int j = i + 1; j < nums.length; j++) {
7 if (nums[i] + nums[j] == target) {
8 return new int[]{i, j};
9 }
10 }
11 }
12 return new int[]{-1, -1};
13}
```

### Time Complexity

Let the number of elements in the array be `n`

** . **This means that:

The first loop will loop through

`(n - 1)`

elements (excluding the element itself)The second loop will loop through

`(n - 2)`

elements (excluding the element itself*and*the previous element)The third loop will loop through

`(n - 3)`

elements (excluding the element itself and the previous elements)etc...

So the time complexity can be modeled with the equation `[(n - 1) + (n - 2) + (n - 3) ... + 2 + 1]`

which can be simplified as `(n * (n - 1)) / 2`

using the sum of natural numbers formula. Simplifying this gives us `(n`

^{2}`/2 - n/2)`

. Remember, big O notation allows you to drop the constants - so we can say the time complexity is O(n^{2}).

### Space Complexity

Since we aren't using any additional data structures, the space complexity is constant, or O(1).

## Approach 2: Using a Map

In this problem we are looking to solve the equation `array[a] + array[b] = target`

where a and b are the solution indices. This equation can be rewritten as `target - array[a] = array[b]`

- meaning when we get to an element, we are looking for the value `target - array[a]`

.

Using this equation, we can iterate through every element and check for it's "complement", or in other words, the number that will solve the equation `target - array[a] = array[b]`

where a is the current index. More simply put, we're saying I am at index a with the value `array[a]`

, is there a number that I have seen that equals `target - array[a]`

?

For this, we need to keep track of all the numbers we have seen as well as the index that number is at. A map (or dictionary, depending on the coding language you are using) is the perfect data structure for this use case.

### Implementation

```
1import java.util.HashMap;
2import java.util.Map;
3
4public int[] twoSum(int[] nums, int target) {
5 if (nums == null) {
6 return new int[]{-1, -1};
7 }
8 Map<Integer, Integer> map = new HashMap<>();
9 for (int i = 0; i < nums.length; i++) {
10 if (map.containsKey(target - nums[i])) {
11 return new int[]{map.get(target - nums[i]), i};
12 }
13 map.put(nums[i], i);
14 }
15 return new int[]{-1, -1};
16}
```

### Time Complexity

If the number of elements in the array is `n`

, in the worst case we are visiting `n`

elements. We are simply visiting every element at most one time, meaning the time complexity is linear, or O(n).

### Space Complexity

In this solution, we are using an auxiliary data structure to keep track of the elements and their index. This means that in the worst case, we are storing `n`

elements, meaning the space complexity is linear, or O(n).

## Conclusion

The two sum problem can be solved in O(n) time and O(n) space. All the code can be found on my github - if you found this helpful, please leave the repo a star!

## Recommended Blogs