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 integersnumsand an integertarget,
returnindices of the two numbers such that they add up totarget.
You may assume that each input would haveexactlyone solution,
and you may not use thesameelement 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)
