Leetcode’s Two Sum Problem Solution

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 exactly one solution, and you may not use the 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 0 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 (0), 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)