Solution: Two Sum

You’re given an array of integers. Write a function that returns a pair of numbers such that they sum up to zero.

Image for post
Image for post
[Alternate problem with a target]
Array of integers is [2, 7, 9, -2].
The pair that sums up to 0 is (2, -2).
2 7 9 -2
-2 2

Solution:

Observe

  1. For a number A, we want to know if such a number B exists, such that A + B = 0.

Algorithm

  1. Create an empty hash map to store the occurrence count for each number in the array.
  2. Iterate through the array.
    For each number A, check if -A is in the hash map.
    If so, return the pair (A, -A). Otherwise, put A in the hash map.

Code

/**
* @param {Array<Number>} nums
* @param {Array<Number>} 2 numbers from nums that add up to 0.
*/
function pairOfZeroSum(nums) {
const hashmap = new Map();
for (let i = 0; i < nums.length; i++) {
if (hashmap.has(-nums[i])) {
return [nums[i], -nums[i]];
}
hashmap.set(nums[i], true);
}
// We should not reach this point since a solution is guaranteed
// to exist.
return [];
}

Complexity Analysis

We visit each number in the array only once. At each visit, we call a couple of hashmap functions, each of which is at O(1) complexity.

Software Engineer @Vedantu, Former Intern @Hackerrank, GSoC @Wikimedia, Former Intern @Vedantu, Codeforces(Expert)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store