2020 Jan Gold Problem 2 Farmer John Solves 3SUM

Official Problem Statement

Farmer John Solves 3SUM

Problem Statement

Farmer John has an array of N (1 ≤ N ≤ 10^5) integers A[1..N]. He wants to find three indices i, j, and k such that A[i] + A[j] + A[k] = 0.

Solution

The solution is to use a two-pointer technique to find the three indices.

int N;
int A[N];

for (int i = 0; i < N; i++) {
    int j = i + 1;
    int k = N - 1;
    while (j < k) {
        int sum = A[i] + A[j] + A[k];
        if (sum == 0) {
            // indices i, j, and k satisfy the condition
            // do something with them
            j++;
            k--;
        } else if (sum < 0) {
            j++;
        } else {
            k--;
        }
    }
}