Algorithms 101 - Two Numbers Sum
Problem Statement
Given an array of distinct integers, find the pair of integers whose sum is equal to the target number, if any.
Arguments
- numbersArray - Array of distinct integers
- targetSum - Target sum number
Solution
Approach 1
- Run 2 for loops, one nested inside the other.
- Check if the sum of the iterating elements equal the target sum.
const twoNumerSum = (numbersArray, targetSum) => {
for (let i = 0; i < numbersArray.length; i++) {
const firstNumber = numbersArray[i];
for (let j = 0; j < numbersArray.length; j++) {
const secondNumber = numbersArray[j];
if (firstNumber + secondNumber === targetSum) {
return [firstNumber, secondNumber];
}
}
}
return [];
};
Time complexity O(n^2)
Space complexity O(1)
Approach 2
- Initiate an empty object & iterate through the input array using a for loop.
- Because we already know the target sum, we can instead search for the unique number, whose summation with the iterating number will be equal to the target sum.
const twoNumerSum = (numbersArray, targetSum) => {
const numbersMap = {};
for (const number of numbersArray) {
const match = targetSum - number;
if (numbersMap[match]) {
return [match, number];
} else {
numbersMap[number] = 'true';
}
}
return [];
};
Time complexity O(n)
Space complexity O(n)
Approach 3
- Input array can be sorted in O(nlogn) using quick sort. Let's do that first.
- Begin summation from the extreme indices and close in. If the sum is less than the target sum, move one index further from the left side, else, the right side.
const twoNumerSum = (numbersArray, targetSum) => {
numbersArray.sort();
let left = 0, right = numbersArray.length - 1;
while (left < right) {
const currentSum = numbersArray[left] + numbersArray[right];
if (currentSum === targetSum) {
return [numbersArray[left], numbersArray[right]];
} else if (currentSum < targetSum) {
left += 1;
} else {
right -= 1;
}
}
return [];
};
Time complexity O(nlogn)
Space complexity O(1)
Link to Code
in node.js. Feel free to raise a PR in any other language.
For the latest updates on the upcoming articles in this series, you can subscribe to the newsletter.