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.
You can assume there will be exactly 1 solution. Each element in the array can only be used once.
Example:
Array of integers is [2, 7, 9, -2].
The pair that sums up to 0 is (2, -2).
Input:
A list of numbers, separated by space.
2 7 9 -2
Output:
2 numbers from the array that sum up to 0.
We will sort the 2 numbers for you so that you can easily compare with our expected output.
-2 2
Solution:
Observe
- For a number A, we want to know if such a number B exists, such that A + B = 0.
Insights:
A brute force approach of 2 nested for loops, one to find A and one to find B should solve the problem, but it is highly inefficient, at O(N²) complexity.
2. Notice that B = -A.
Insights:
Instead of making a 2nd nested for loop to find B, we can use a hash map to quickly check if B exists in the array.
Algorithm
- Create an empty hash map to store the occurrence count for each number in the array.
- 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.
Hence, the overall complexity is O(N).