The 2-SUM Problem

Internal

• Hash Table
• Sorting Algorithms
• Binary Search

Overview

Given as input an input of n numbers, in no particular order, and a target sum t, find all pairs of integers that sum to t.

The naive solution would be to double loop over the array in O(n²) running time.

The better solution (that comes with an extra space requirement, though) is to insert all numbers in a hash table and then do a second pass where for each number we look to see if (t - x_i) exists in the table. This is a O(n) solution.