Three Sum Editorial

Practice Problem Link: Three Sum | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given array A, find all unique triplets in the array whose sum is equal to zero.

Naive Approach

In this approach, we can iterate over all possible triplets of the given array and check if each triplet is valid, push them into an appropriate data structure such as a set of tuples, to remove duplicates.

Analysis

• Time Complexity: O(n³ * logn)
• Space Complexity: O(n²)

Implementation

C++

vector<vector<int>> threeSum(vector<int> &A) {
   int n = (int)A.size();
   set<vector<int>> solutionSet;
   for (int i = 0; i < n; i++) {
       for (int j = i + 1; j < n; j++) {
           for (int k = j + 1; k < n; k++) {
               if(A[i] + A[j] + A[k] == 0) {
                   vector<int> triples = {A[i], A[j], A[k]};
                   sort(triples.begin(), triples.end());
                   solutionSet.insert(triples);
               }
           }
       }
   }
   vector<vector<int>> answer;
   for (auto x: solutionSet) {
       answer.push_back(x);
   }
   return answer;
}

Java

class Solution {
   List<List<Integer>> threeSum(int[] A) {
       int n = A.length;
       HashSet<ArrayList<Integer>> solutionSet = new HashSet<ArrayList<Integer>>();
       for(int i = 0; i < n; i++) {
           for(int j = i + 1; j < n; j++) {
               for(int k = j + 1; k < n; k++) {
                   if(A[i] + A[j] + A[k] == 0) {
                       ArrayList<Integer> triples = new ArrayList<Integer>();
                       triples.add(A[i]);
                       triples.add(A[j]);
                       triples.add(A[k]);
                       Collections.sort(triples);
                       solutionSet.add(triples);
                   }
               }
           }
       }
       ArrayList<List<Integer>> answer = new ArrayList<List<Integer>>();
       for (ArrayList<Integer> x: solutionSet) {
           answer.add(x);
       }
       return answer;
   }
}

Optimal Approach

Observe that sorting the array does not change the answer. It is well known that in multiple problems if a list is sorted, we can exploit its properties to our advantage since various algorithms work efficiently when the list is sorted. So, we can approach the problem after sorting the array and thinking about what algorithms works especially for such arrays (hint: Binary Search, Two Pointers, etc).

Here also, we first sort the array. In the sorted array, we fix one index, say i in the array, and on the rest of the array, we apply the 2 pointers algorithm to search for the sum -(A[i]). As soon, as a triplet is found, store the triplet in an appropriate container. To get rid of the same triplets, we can skip the iteration if the current and next elements are the same, and move the pointers appropriately.

Analysis:

• Time Complexity: O(n²)
• Space Complexity: O(1)

Implementation

C++

vector<vector<int>> threeSum(vector<int> &A) {
   int n = A.size();
   sort(A.begin(), A.end());
   vector<vector<int>> answer;
   for (int i = 0; i < n; i++) {
       int j = i + 1;
       int k = n - 1;
       if(i > 0 && A[i] == A[i - 1]) {
           continue;
       }
       while(j < k) {
           if(k < (n - 1) && A[k] == A[k + 1]) {
               k--;
               continue;
           }
           if(A[i] + A[j] + A[k] > 0) {
               k--;
           } else if(A[i] + A[j] + A[k] < 0) {
               j++;
           } else {
               vector<int> triples = {A[i], A[j], A[k]};
               sort(triples.begin(), triples.end());
               j++;
               k--;
               answer.push_back(triples);
           }
       }
   }
   return answer;
}

Java

class Solution {
   List<List<Integer>> threeSum(int[] A) {
       int n = A.length;
       Arrays.sort(A);
       ArrayList<List<Integer>> answer = new ArrayList<List<Integer>>();
       for (int i = 0; i < n; i++) {
           int j = i + 1;
           int k = n - 1;
           if(i > 0 && A[i] == A[i - 1]) {
               continue;
           }
           while (j < k) {
               if(k < (n - 1) && A[k] == A[k + 1]) {
                   k--;
                   continue;
               }
               if(A[i] + A[j] + A[k] > 0) {
                   k--;
               } else if(A[i] + A[j] + A[k] < 0) {
                   j++;
               } else {
                   ArrayList<Integer> triples = new ArrayList<Integer>();
                   triples.add(A[i]);
                   triples.add(A[j]);
                   triples.add(A[k]);
                   Collections.sort(triples);
                   j++;
                   k--;
                   answer.add(triples);
               }
           }
       }
       return answer;
   }
}