Four Sum Editorial

Practice Problem Link: Four Sum | Practice Problem

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

Problem Statement

Given an array A and a target value, find all unique quadruple such that their sum is equal to the target value.

Naive Approach

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

Analysis

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

Implementation

C++

vector<vector<int>> fourSum(vector<int> &a, int target) {
   vector<vector<int>> answer;
   set<vector<int>> removeDuplicates;
   int n = a.size();
   for(int i = 0; i < n; i++) {
       for(int j = i + 1; j < n; j++) {
           for(int k = j + 1; k < n; k++) {
               for(int l = k + 1; l < n; l++) {
                   int sum = a[i] + a[j] + a[k] + a[l];
                   if(sum == target) {
                       vector<int> list = {a[i], a[j], a[k], a[l]};
                       sort(list.begin(), list.end());
                       removeDuplicates.insert(list);
                   }
               }
           }
       }
   }
   for(auto x: removeDuplicates) {
       answer.push_back(x);
   }
   return answer; 
}

Java

class Solution {
   List<List<Integer>> fourSum(int[] A, int target) {
       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++) {
                   for (int l = k + 1; l < n; l++) {
                       if(A[i] + A[j] + A[k] + A[l] == target) {
                          ArrayList<Integer> list = new ArrayList<Integer>();
                          list.add(A[i]);
                          list.add(A[j]);
                          list.add(A[k]);
                          list.add(A[l]);
                          Collections.sort(list);
                          solutionSet.add(list);
                       }
                   }
               }
           }
       }
       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).

Logic:

• Here also, we first sort the array.
• In the sorted array, we fix two indexes, say i and j in the array, and on the rest of the array, we apply the 2 pointers algorithm to search for the sum = target  - (A[i] + A[j]).
• As soon, as a quadruple is found, store the quadruple in an appropriate container.
• To get rid of the same quadruples, 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>> fourSum(vector<int> &a, int target) {
   int n = a.size();
   sort(a.begin(), a.end());
   vector<vector<int>> answer;
   for (int i = 0; i < n; i++) {
       if(i != 0 && a[i] == a[i - 1]) {
           continue;
       }
       for (int j = i + 1; j < n; j++) {
           if(j != i + 1 && a[j] == a[j - 1]) {
               continue;
           }
           int first = j + 1, last = n - 1;
           while (first < last) {
               int sum = a[i] + a[j] + a[first] + a[last];
               if(sum == target) {
                   vector<int> list;
                   list.push_back(a[i]);
                   list.push_back(a[j]);
                   list.push_back(a[first]);
                   list.push_back(a[last]);
                   answer.push_back(list);
                   while (first < last && a[first] == a[first+1]) {
                       first++; 
                   }
                   while (first < last && a[last] == a[last-1]) {
                       last--;
                   }
                   first++;
                   last--;
               } else if(sum < target) {
                   first++;
               } else {
                   last--;
               }
           }
       }
   }
   return answer;
}

Java

class Solution {
   List<List<Integer>> fourSum(int[] a, int target) {
       int n = a.length;
       Arrays.sort(a);
       List<List<Integer>> answer = new ArrayList<>();
       for (int i = 0; i < n; i++){
           if(i != 0 && a[i] == a[i-1]) {
               continue;
           }
           for (int j = i + 1; j < n; j++) {
               if(j != i + 1 && a[j] == a[j-1]) {
                   continue;
               }
               int first = j + 1, last = n - 1;
               while (first < last) {
                   int sum = a[i] + a[j] + a[first] + a[last];
                   if(sum == target) {
                       List<Integer> list = new ArrayList<>();
                       list.add(a[i]);
                       list.add(a[j]);
                       list.add(a[first]);
                       list.add(a[last]);
                       answer.add(list);
                       while (first < last && a[first] == a[first+1]) {
                           first++; 
                       }
                       while (first < last && a[last] == a[last-1]) {
                           last--;
                       }
                       first++;
                       last--;
                   }
                   else if(sum < target) {
                       first++;
                   }
                   else {
                       last--;
                   }
               }
           }
       }
       return answer;
   }
}