3 Sum

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg Facebook Google Microsoft Oracle Qualtrics Tesla VMware
Array Two PointerViews 2193

In 3 Sum problem, we have given an array nums of n integers, find all the unique triplets that sum up to 0.

Example

Input:
nums = {-1, 0, 1, 2, -1, -4}
Output:
{-1, 0, 1}, {-1, 2, -1}

3 Sum

Naive Approach for 3 Sum problem

The Brute force approach to solve the problem is to test all the possible triplets and pick those that sums up to zero.
This could be achieved using three nested loops.

  1. Create a HashSet to store the triplets with sum 0.
  2. Run a loop for i = 0 to (n – 1), where n is the number of elements in the array.
  3. Run a nested loop for j = (i + 1) to (n – 1).
  4. Nest one more loop for k = (j + 1) to (n – 1).
  5. These three loop forms a unique triplet, nums[i], nums[j] and nums[k]. The sum of the triplet is (nums[i] + nums[j] + nums[k]). If the sum is zero, add this triplet(i, j, k) to the triplets HashSet.
  6. All the triplets summing to zero are present in HashSet, so print the content of HashSet.

JAVA Code for 3 Sum

public class ThreeSum {
    private static void printUniqueTriplets(int[] nums) {
        int n = nums.length;
        // Created a set of triplets to avoid duplicates
        HashSet<Triplet> triplets = new HashSet<>();
        
        // Use 3 nested loop to check all the possible combinations
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    // If this triplet sums to zero, add it in the set
                    int sum = nums[i] + nums[j] + nums[k];
                    if (sum == 0) {
                        triplets.add(new Triplet(nums[i], nums[j], nums[k]));
                    }
                }
            }
        }

        // Print the unique triplets
        for (Triplet triplet : triplets) {
            System.out.println(triplet.ele[0] + " " + triplet.ele[1] + " "
                    + triplet.ele[2]);
        }
    }

    public static void main(String[] args) {
        // Example
        int nums[] = new int[]{-1, 0, 1, 2, -1, -4};
        printUniqueTriplets(nums);
    }

    // class representing a triplet
    static class Triplet {
        int ele[];

        public Triplet(int first, int second, int third) {
            ele = new int[3];
            ele[0] = first;
            ele[1] = second;
            ele[2] = third;
            // Store the triplets in ascending order, so that this could be used 
            // in checking duplicates
            Arrays.sort(ele);
        }
        
        // Two triplets are equal if elements in them are same 
        @Override
        public boolean equals(Object o) {
            Triplet t = (Triplet) o;
            return (Arrays.compare(ele, t.ele) == 0);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(ele);
        }
    }
}
-1 -1 2
-1 0 1

C++ Code for 3 Sum

#include <bits/stdc++.h> 
using namespace std; 

// structure representing a triplet
struct Triplet {
    int ele[3];
    
    bool operator==(const Triplet& t) const { 
        return (this->ele[0] == t.ele[0] && this->ele[1] == t.ele[1] && this->ele[2] == t.ele[2]);
    }
};

// custom hash function for triplet
class MyHash {
    public:
    size_t operator()(const Triplet& t) const { 
        return t.ele[0] + 10 * t.ele[1] + 100 * t.ele[2]; 
    } 
};

void printUniqueTriplets(int *nums, int n) {
    // Created a set of triplets to avoid duplicates
    unordered_set<Triplet, MyHash> triplets;
    
    // Use 3 nested loop to check all the possible combinations
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                int sum = nums[i] + nums[j] + nums[k];
                // If this triplet sums to zero, add it in the set
                if (sum == 0) {
                    Triplet triplet;
                    int e[3];
                    e[0] = nums[i];
                    e[1] = nums[j];
                    e[2] = nums[k];
                    sort(e, e + 3);
                    triplet.ele[0] = e[0];
                    triplet.ele[1] = e[1];
                    triplet.ele[2] = e[2];
                    triplets.insert(triplet);
                }
            }
        }
    }
    
    // Print the unique triplets
    for (auto itr = triplets.begin(); itr != triplets.end(); itr++) {
        cout<<itr->ele[0]<<" "<<itr->ele[1]<<" "<<itr->ele[2]<<endl;
    }
}

int main() {
    // Example
    int nums[] = {-1, 0, 1, 2, -1, -4}; 
    printUniqueTriplets(nums, sizeof(nums) / sizeof(nums[0]));
}
-1 -1 2
-1 0 1

Complexity Analysis

Time Complexity = O(n3
Space Complexity = O(1)
where n is the number of elements in the array.

Optimal Approach for 3 Sum problem

The better approach is to use 3 pointer method.

  1. Sort the array in ascending order.
  2. For an element at index i, try to make a sum of -nums[i] (negative of nums[i]) with two elements from the elements ahead of it, so that the triplet sums to zero.
  3. Two pointer approach is applicable here to find the required sum(-nums[i]) because the array is sorted.
  4. If there exists two elements that sum up to required sum, add the triplet (two elements and nums[i]) to the answer set.
  5. Print the answer set.

JAVA Code for 3 Sum

import java.util.Arrays;
import java.util.HashSet;

public class ThreeSum {
    private static void printUniqueTriplets(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);

        HashSet<Triplet> triplets = new HashSet<>();

        for (int i = 0; i < n; i++) {
            int req = -nums[i];
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == req) {
                    triplets.add(new Triplet(nums[i], nums[left], nums[right]));
                    // Check for more triplets
                    left++;
                    right--;
                } else if (sum < req) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        // Print the unique triplets
        for (Triplet triplet : triplets) {
            System.out.println(triplet.ele[0] + " " + triplet.ele[1] + " "
                    + triplet.ele[2]);
        }
    }

    public static void main(String[] args) {
        int nums[] = new int[]{-1, 0, 1, 2, -1, -4};
        printUniqueTriplets(nums);
    }

    // class representing a triplet
    static class Triplet {
        int ele[];

        public Triplet(int first, int second, int third) {
            ele = new int[3];
            ele[0] = first;
            ele[1] = second;
            ele[2] = third;
            // Store the triplets in ascending order, so that this could be used
            // in checking duplicates
            Arrays.sort(ele);
        }

        // Two triplets are equal if elements in them are same
        @Override
        public boolean equals(Object o) {
            Triplet t = (Triplet) o;
            return (Arrays.compare(ele, t.ele) == 0);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(ele);
        }
    }
}
-1 -1 2
-1 0 1

C++ Code for 3 Sum

#include <bits/stdc++.h> 
using namespace std; 

// structure representing a triplet
struct Triplet {
    int ele[3];
    
    bool operator==(const Triplet& t) const { 
        return (this->ele[0] == t.ele[0] && this->ele[1] == t.ele[1] && this->ele[2] == t.ele[2]);
    }
};

// custom hash function for triplet
class MyHash {
    public:
    size_t operator()(const Triplet& t) const { 
        return t.ele[0] + 10 * t.ele[1] + 100 * t.ele[2]; 
    } 
};

void printUniqueTriplets(int *nums, int n) {
    sort(nums, nums + n);
    
    // Created a set of triplets to avoid duplicates
    unordered_set<Triplet, MyHash> triplets;
    
    for (int i = 0; i < n; i++) {
        int req = -nums[i];
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == req) {
                // Add this triplet to the set
                Triplet triplet;
                int e[3];
                e[0] = nums[i];
                e[1] = nums[left];
                e[2] = nums[right];
                sort(e, e + 3);
                triplet.ele[0] = e[0];
                triplet.ele[1] = e[1];
                triplet.ele[2] = e[2];
                triplets.insert(triplet);
                // Check for more triplets
                left++;
                right--;
            } else if (sum < req) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    // Print the unique triplets
    for (auto itr = triplets.begin(); itr != triplets.end(); itr++) {
        cout<<itr->ele[0]<<" "<<itr->ele[1]<<" "<<itr->ele[2]<<endl;
    }
}

int main() {
    // Example
    int nums[] = {-1, 0, 1, 2, -1, -4}; 
    printUniqueTriplets(nums, sizeof(nums) / sizeof(nums[0]));
}
-1 -1 2
-1 0 1

Complexity Analysis

Time Complexity = O(n2
Space Complexity = O(1)
where n is the number of elements in the array.

References

Translate »