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.

Naive Solution O(n²)

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

O(n log n) with No Additional Space Requirements=

A better solution would be to sort the array O(n log n), then do a linear scan over the array and for each x_i element search using binary search for t - x_i. Binary search on a sorted array is done in O(log n) time, so the total complexity is O(n log n) + n O(log n) = O(n log n).

O(n) with Additional Space Requirements=

A better running time 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.