Problem

Given an array of integer write an algorithm to find 3 elements that sum to a zero. In short a+b+c = 0.

OR

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output:[[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output:[[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Solution

Method 1 - Brute Force

Use 3 nested loops and find the 3 elements which sum to 0.

Code

Java
public List<List<Integer>> threeSum(int[] nums) {
	List<List<Integer>> triplets = new ArrayList<>();
    for (int i = 0; i < a.length; i++) {
        for (int j = i + 1; j < a.length; j++) {
            for (int k = j + 1; k < a.length; k++) {
                if (a[i] + a[j] + a[k] == 0) {
                    triplets.add(List.of(a[i], a[j], a[k]));
                }
            }
        }
    }
    return triplets;
}

Complexity

  • ⏰ Time complexity: O(n^3)
  • 🧺 Space complexity: O(1)

Method 2 - Use Hashing

  • Use the other loop to fix the one element at a time.
  • Now required_sum is (with two elements) = -fixed element.
  • Create a HashSet, Iterate through rest of the array.
  • For current_element, remain_value = required_sum – current_element.
  • Check if remain_value in the HashSet, we have found our triplets else add current_element to the hashset.

Code

Java
//we need to find a + b + c = 0
//OR reduce the problem c = -(a+b)

public static void find(int[] x) {
    for (int i = 0; i < x.length; i++) {
        int a = x[i];
        HashSet <Integer> set = new HashSet <> ();

        for (int j = i + 1; j < x.length; j++) {
            int b = x[j];
            int c = -(a + b);
            if (set.contains(c)) {
                System.out.println("Found 3 elements whose sum is = 0");
                System.out.println("Elements are " + a + " " + b + " " + c);
                return;
            } else
                set.add(b);
        }
    }
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(n)

Method 3 - Using Sorting and Two Pointer Approach

Code

Java
private static List<List<Integer>> threeSum(int[] a) {
	List<List<Integer>> triplets = new ArrayList<>();

	Arrays.sort(a);
	for(int i = 0; i < a.length-2; i++) {
		// Skip duplicates
		if(i > 0 && a[i] == a[i-1]) {
			continue;
		}

		// Fix one number
		int firstNum = a[i];

		// Use Two-sum approach to get the other two numbers
		int left = i+1, right = a.length-1;
		while(left < right) {
			int sum = firstNum + a[left] + a[right];
			if(sum == 0) {
				triplets.add(Arrays.asList(firstNum, a[left], a[right]));
				left++;
				right--;

				// Skip duplicates
				while(left < right && a[left] == a[left-1]) {
					left++;
				}
				while(left < right && a[right] == a[right+1]) {
					right--;
				}
			} else if(sum < 0) {
				left++;
			} else {
				right--;
			}
		}
	}

	return triplets;
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)