Leetcode’s Two Sum Problem Solution


Olorunfemi Akinlua

JavaScript

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)

 

Views: 2

Olorunfemi Akinlua

He is boasting over five years of experience in JavaScript, specializing in technical content writing and UX design. With a keen focus on programming languages, he crafts compelling content and designs user-friendly interfaces to enhance digital experiences across various domains. You can connect with him on LinkedIn.

Can't find what you're searching for? Let us assist you.

Enter your query below, and we'll provide instant results tailored to your needs.

If my articles on GoLinuxCloud has helped you, kindly consider buying me a coffee as a token of appreciation.

Buy GoLinuxCloud a Coffee

For any other feedbacks or questions you can send mail to admin@golinuxcloud.com

Thank You for your support!!

Leave a Comment

GoLinuxCloud Logo


We try to offer easy-to-follow guides and tips on various topics such as Linux, Cloud Computing, Programming Languages, Ethical Hacking and much more.

Programming Languages

JavaScript

Python

Golang

Node.js

Java

Laravel