LeetCode 15 – 3Sum

Posted on December 25, 2013

Last updated on December 25, 2013

Solution to LeetCode 3Sum problem.

Naive way is \(O(n^3)\) – look at all triplets. We can improve this to \(O(n^2)\) by first sorting the array, and traversing it with three pointers \(0 \leq i \lt j \lt k \lt N\). For every choice of \(i\), use the 2SUM algorithm on the sorted subarray, and find \(j\),\(k\) such that \(A(j) + A(k) = C - A(i)\), where in this question variant \(C = 0\). We must take care to not print duplicate elements.

public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
  Arrays.sort(num);
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  for(int i = 0; i < num.length-2; i++){
    int j = i+1;
    int k = num.length-1;
    while(j < k){
      int sum = num[i] + num[j] + num[k];
      if(sum < 0) j++;
      else if(sum == 0){
        // If the sum is zero, have to skip over equal values
        // for num[j] and num[k] so that we don't get duplicates
        Integer[] arr = new Integer[]{num[i],num[j],num[k]};
        result.add(new ArrayList<Integer>(Arrays.asList(arr)));
        do{ j++; } while (j < k && num[j] == num[j-1]);
        do{ k--; } while (j < k && num[k] == num[k+1]);
      }
      else k--;
    }
    // Move ahead the first tuple element so that we don't
    // try another 3-tuple with the same first element.
    while(i < num.length-1 && num[i] == num[i+1]) i++;
  }
  return result;
}
3SUM
Markdown SHA1: 599dee13a7ee0d66e6e6e34d2f01f2684873857f