Table of Contents

## Introduction

Data structures and algorithms are an essential part of a developer’s life where understanding how to store data (structures) and how to efficiently process or access the data (algorithms) is a must. Therefore, solving and practicing data structures and algorithms helps us build a more efficient and resilient application.

In this article, we will discuss one of many leetcode data structures - the pair sums or two sums problem - and show the different approaches (and their possible letdowns) to solving them.

## Pair Sums Problem

The pair sums leetcode problem goes thus;

“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

**, and you may not use the**

*exactly*one solution*same*element twice. You can return the answer in any order.”

An example of how the problem goes;

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

So, let’s get cracking.

## Method 1: Using Brute Force (`nested for loops`

)

As we start developing, it is always great to start with the simplest and first approach that comes to mind - even if inefficient. As the section heading states, the `pair sum`

problem can be solved using brute force, where we use two nested iterations to achieve our goal.

Before we illustrate how we will approach this, we need to understand that we have two inputs to our potential algorithm - the `integer`

array and the `target`

value. The integer array contains the numbers we will check through to see if two of them added up to the `target`

value.

Now to solve the problem, we will loop through the array the first time to get the index and index’s element, then loop through again the same array again but from an index forward. If first loop current index is `1`

, second loop iteration will start from index `2`

.

So, within the second loop, we will check if the element of the first loop’s index plus the element of the second loop’s index equal the `target`

value. If true, we return the index of both loops at the time.

```
function pairSum(numbers, target) {
for (let i = 0; i < numbers.length; i++) {
for (let j = i + 1; j < numbers.length; j++) {
if (numbers[i] + numbers[j] == target) {
return [i, j];
}
}
}
}
console.log(pairSum([2, 7, 11, 15], 9));
```

Output

```
[ 0, 1 ]
```

As you can see element at index ` and `

`1`

(`2`

and `7`

) add up to the `target`

value, `9`

.

To show how it works more intricately, we can change the position of the integers within the array and log the indices before the `if`

statement to show what’s going on within the `brute force`

algorithm we have written

```
function pairSum(numbers, target) {
for (let i = 0; i < numbers.length; i++) {
for (let j = i + 1; j < numbers.length; j++) {
console.log(i, j);
if (numbers[i] + numbers[j] == target) {
return [i, j];
}
}
}
}
console.log(pairSum([11, 15, 2, 7], 9));
```

Output

```
0 1
0 2
0 3
1 2
1 3
2 3
[ 2, 3 ]
```

As you can see within the output, the first number indicates the first loop index and the second number indicates the second loop index. Also, since we are still in first loop index (`), `

`1, 2, 3`

are checked and are seen to not fulfill the conditional statement, and then the code moves to the next index of the first loop, and `2, 3`

are checked, and on and on.

This approach is O(n2) and is largely inefficient.

## Method 2: Using Objects

For an efficient approach, we can make use of objects (a key and pair data structure). We can make use of `forEach`

to create an object (`indices`

) with a key and pair relationship, and then use another `for`

loop to access the `number`

array, and then calculate the `complement`

binding.

Afterward, check the `complement`

value within the `indices`

object and compare it to the `undefined`

and the `index`

value. Whatever `complement`

value is true based on the condition, then return the `index`

and the `indices`

complement value.

```
function pairSums(numbers, target) {
const indices = {};
numbers.forEach((item, index) => {
indices[item] = index;
});
console.log(indices);
for (let index = 0; index < numbers.length; index++) {
const complement = target - numbers[index];
if (
indices[complement] !== undefined &&
indices[complement] !== index
) {
return [index, indices[complement]];
}
}
}
console.log(pairSums([2, 7, 11, 15], 9));
```

Output

```
[ 0, 1 ]
```

## Method 3: Using Maps

In this approach, we will make use of the `Map`

object to create a `key/value`

pair relationship, and instead of using the `forEach`

method, we can make use of the `set`

method to add the numbers and the index to the map, to be checked using the `has`

method. Overall, the same approach as the previous section using the `complement`

binding.

```
function pairSum(number, target) {
const indices = new Map();
for (let index = 0; index < number.length; index++) {
const complement = target - number[index];
if (indices.has(complement)) {
return [indices.get(complement), index];
}
indices.set(number[index], index);
}
}
console.log(pairSum([2, 7, 11, 15], 9));
```

Output

```
[ 0, 1 ]
```

This approach is O(n).

## Summary

The **pair sums** leetcode problem is an interesting one, and the use of the three approaches solves the problem, but the last two are more reasonable approaches to solve the problem.

## References

Two Sum - LeetCode

Array.prototype.map() - JavaScript | MDN (mozilla.org)