Find 3 numbers in an array adding up to a given sum S.

Question

lamont · Accepted Answer

This is called the 3SUM problem. Given an array a[n], find three elements a[i] + a[j] + a[k] = S (for distinct values of i, j, and k). The standard solution is O(n^2):

sort(a, n);
for (int i = 0; i  s)
            k--;
        else
            output("Solution found: a[%d] + a[%d] + a[%d] = %g
", i, j, k, result);
    }
}

duong · Answer

After sorting the input array in O(nlogn) time, you can solve 2-sum problem in O(n) time using two-pointer technique. Then, to solve 3-sum problem, just iterate over all n elements in the array, each time using O(n) time 2-sum algorithm. This results in overall O(n^2) time algorithm.

Google

Google interview question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches