3Sum — LeetCode Challenge

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution:

Method 1: Brute Force

• Approach: The simple approach runs three loops and checks one by one that the sum of the three elements is zero or not. If the sum of three elements is zero then add all the three elements in the list and add it back to the list of results.
• Algorithm:

1. Run three nested loops with loop counter i, j, k
2. The three loops will run from 0 to n-3 and second loop from i+1 to n-2 and the third loop from j+1 to n-1. The loop counter represents the three elements of the triplet.
3. check if the sum of elements at i^th, j^th, k^th is equal to zero or not. If yes print then adds all the three elements to the list and back to the results.

Method 2: The second method uses the process of Hashing and is solved at a lesser time of O(n^2).

• Approach: This involves traversing through the array. For every element arr[i], find a pair with the sum “-arr[i]”. This problem reduces to pairs sum and can be solved in O(n) time using hashing.
• Algorithm:

1. Create a hashmap to store a key-value pair.
2. Run a nested loop with two loops, outer loop from 0 to n-2 and the inner loop from i+1 to n-1
3. Check if the sum of ith and jth element multiplied with -1 is present in the hashmap or not
4. If the element is present in the hashmap, print the triplet else insert the j^th element in the hashmap.

Method 3: This method uses Sorting to arrive at the correct result and is solved in O(n^2) time.

• Approach: For every element check that there is a pair whose sum is equal to the negative value of that element.
• Algorithm:

1. Sort the array in ascending order.
2. Traverse the array from start to end.
3. For every index i, create two variables l = i + 1 and r = n — 1
4. Run a loop until l is less than r if the sum of array[l], array[r] is equal to zero then print the triplet and break the loop
5. If the sum is less than zero then increment the value of l, by increasing the value of l the sum will increase as the array is sorted, so array[l+1] > array [l]
6. If the sum is greater than zero then decrement the value of r, by increasing the value of l the sum will decrease as the array is sorted, so array[r-1] < array [r].

Happy Coding!!!