2-Sum and 3-Sum

Posted by Beetle B. on Sun 20 July 2014

2-Sum

Problem Statement

Given a set of \(N\) integers, find how many pairs sum to 0.

Brute Force

Sum all pairs and count whichever sum to 0. This is \(O(N^{2})\).

3-Sum

Problem Statement

Given a set of \(N\) integers, find how many triplets sum to 0.

Brute Force

Sum all triplets and count whichever sum to 0. This is \(O(N^{3})\).

Sort & Search

First sort all the numbers in \(O(N\log N)\) time. Then loop through your sorted list. For each pair of integers, we want to see if the required third integer exists in the list. A simple binary search will give it to you.

This is \(O(N^{2}\log N)\).

\(O(N^{2})\)

First sort all the numbers in \(O(N\log N)\) time. Then loop through the list. For each element \(a\), we want to know if \(b\) and \(c\) exist such that \(-a=b+c\). This can be done in linear time: Start traversing the list from the left and assign the number to \(b\). We know the desired \(c\). Start searching for \(c\) by traversing from the right.

For the next \(b\), we continue searching for \(c\) from the right from our previous stopping point. We can do this as the list is sorted. This way we find all instances of \(-a=b+c\) in linear time with fixed \(a\).

Overall, this is \(O(N^{2})\).