The Two Sum problem is a classic problem frequently encountered in coding interviews and algorithm challenges. It tests your ability to efficiently find two numbers in an array that sum up to a given target. In this blog post, we’ll explore different approaches to solving this problem, highlighting their time and space complexities.

### Problem Statement

Given an array of integers `nums`

and an integer, return the indices of the two numbers such that they add up to `target`

. Each input is guaranteed to have exactly one solution, and you may not use the same element twice.

**Example:**

```
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
```

### Solution 1: Brute Force Approach

#### Description

The brute force approach involves checking every possible pair of numbers to see if they add up to the target. This method is straightforward but not the most efficient.

#### Algorithm

- Iterate through each element in the array.
- For each element, iterate through the remaining elements to check if the sum of the current element and another element equals the target.
- If such a pair is found, return their indices.

Code

```
def twoSum(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
```

#### Time Complexity

The time complexity of this approach is O(n^2) due to the two nested loops iterating through the array.

#### Space Complexity

The space complexity is O(1) since no additional space is used apart from a few variables.

#### Pros and Cons

**Pros:**Simple to understand and implement.**Cons:**Inefficient for large arrays due to its quadratic time complexity.

### Solution 2: Hash Map Approach

#### Description

The hash map approach utilizes a dictionary (hash map) to store indices of elements as we iterate through the array. This allows us to check if the complement of the current component (i.e., `target - current_element`

) is already present in the hash map.

#### Algorithm

- Create an empty dictionary to store elements and their indices.
- Iterate through the array, and for each element, calculate its complement by subtracting the element from the target.
- Check if the complement is already in the dictionary:
- If it is, return the indices of the complement and the current element.
- If it is not, store the current element and its index in the dictionary.

#### Code

```
def twoSum(nums, target):
num_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_map:
return [num_map[complement], i]
num_map[num] = i
```

#### Time Complexity

The time complexity of this approach is O(n) as each lookup and insertion in the hash map takes constant time, and we only traverse the array once.

#### Space Complexity

The space complexity is O(n) due to the hash map that stores elements and their indices.

#### Pros and Cons

**Pros:**Efficient with linear time complexity and suitable for large arrays.**Cons:**Requires additional space for the hash map.

### Comparison

Approach | Time Complexity | Space Complexity | Pros | Cons |
---|---|---|---|---|

Brute Force | O(n^2) | O(1) | Simple to implement | Inefficient for large arrays |

Hash Map | O(n) | O(n) | Efficient and suitable for large arrays | Requires extra space |

### Conclusion

The Two Sum problem can be tackled using various methods, each with its own advantages and trade-offs. The brute force approach, while simple, is not ideal for large datasets due to its quadratic time complexity. The hash map approach, although requiring extra space, provides a more efficient solution with linear time complexity.

## Leave a Reply