## DEV Community is a community of 723,552 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. Brijesh Shah

Posted on • Originally published at tuls.in

# 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

1. numbersArray - Array of distinct integers
2. 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)