Solution: Two Sum


[Alternate problem with a target]



A list of numbers, separated by space.

2 numbers from the array that sum up to 0.



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

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.

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.


  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.


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).
