DEV Community

Cover image for Algorithms 101 - Two Numbers Sum
Brijesh Shah
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 [];

};
Enter fullscreen mode Exit fullscreen mode

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 [];

};
Enter fullscreen mode Exit fullscreen mode

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 [];

};
Enter fullscreen mode Exit fullscreen mode

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.

Discussion (0)