3 Sum - Leetcode #15 Short & Simple Solution
Updated: Jun 6, 2022
Problem Statement
This is another article in the series leetcode problem solutions and this article is a solution to leetcode 15 three sum problem.
We solved the two sum problem in our earlier article, and this problem in some ways is a continuation of the two sum problem. So, if you have not yet solved the two sum problem we advice you to do so because it will help you understand the 3 sum problem better.
Given an array of integers, nums, return all the triplets in the given array nums[i], nums[j], nums[k] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice: 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]]Example 2:
Input: nums = [0]
Output: []Solution
Let us try to understand the problem statement. The first part of the problem statement is clear, we are asked to find out all the triplets in the given array whose sum is equal to zero. A triplet is nothing but a set of three numbers in the given array. For example, if nums=[1,2, 3,4] is the given array, [1,2,3] [2,3,4] [1,3,4] etc are its triplets.
What does the condition i != j, i != k, and j != k mean?
It means that we are not allowed to reuse any number from the array within a triplet. Example, for the given array nums = [1,2,3,4], triplets [1,1,1] or [1,1,2] or [1,2,2] etc are not considered valid triplets.
The last condition that we need to consider is that we cannot have duplicate triplets in our final result. Example if [-2,-2,0,2] is the given array, we can only consider one of [-2,0,2] from indexes 0, 2, 3 and [-2,0,2] from indexes 1, 2, 3 in our final result.
Solution 1: Brute Force
The most simple and straight forward solution to this problem is to find every possible triplet from the given array, see if its sum is equal to zero and return the result (ensuring there are no duplicate triplets in the result).
This algorithm involves the following steps:
Use three loops to generate all possible triplets for the given array, with each loop variable keeping track of 1 triplet element each.
Next we calculate the sum for each triplet generated in step 1.
If the sum is equal to 0 we need to check if it is a unique triplet (not already in our result set). We can ensure the triplets in our result set are unique by sorting the triplets and adding it to a hashmap (hashmap overwrites data if same value is written to the same key multiple times thereby eliminating duplicates).
Once we have added all the triplets whose sum is equal to 0 into the hashmap, we iterate through the hashmap and add it to our result array.
Finally we return the result array.
Implementation
Below is the implementation for this solution:
Language: Go
Language: Java
Complexity Analysis
Time Complexity: O(n^3)
Time complexity is O(n^3) since the algorithm uses 3 loops to arrive at the result.
Space Complexity: O(k)
Space complexity is O(k) since we use hashmap to store unique triplets. k here is the number of unique triplets with sum = 0 for the given array.
Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:
Solution 2: Efficient Solution
We can sort the given array and use the three pointer approach to improve the time complexity of our solution as compared to the previous approach.
The idea is to sort the array first, then run two loops to process the triplets. We fix the outer loop and move the two pointers (indexes) of the inner loop inwards to arrive at the result.
The intuition behind this algorithm is simple, when we sort the array all the duplicate elements are grouped together. And if we use two pointers from left and right to traverse the array while processing the triplets, we can easily avoid duplicate triplets that would occur because of these duplicate elements.
For example is nums = [-2, 1, -3, 5, -3, 5] is the given array, when we sort this array we get: nums = [-3, -3, -2, 1, 5, 5]. As you can see all the duplicate elements [-3, -3] and [5,5] are grouped together. If were to consider all of these duplicate elements, it would result duplicate triplets like [-3, -2, 5] and [-3, -2, 5]. We can easily avoid this if we use two pointers to traverse the array from either sides (one from start and one from end). We process only the 1st element and skip all the duplicate elements that appear after it.
For the given input array nums of size n this approach does the following steps:
First step is to sort the given array nums. Sorting the array helps us identify duplicate triplets using our loops by skipping certain numbers that would result in duplicate triplets. This helps us avoid using a hashmap to identify the duplicates (like in solution 1) there by improving the space complexity(Keep reading to know how duplicate triplets can be skipped). Also sorting the array helps efficiently increment/decrement our index variables depending on whether the sum is less than or greater than 0.
Next we need two loops. Outer loop index num1Idx represents the index of the first element in the triplet. Inner loop contains two indexes num2Idx and num3Idx representing the indexes of the 2nd and 3rd triplet elements respectively.
Initially num1Idx points to the first element in the given array and num2Idx, num3Idx point to the 2nd and last elements in the given array. We fix the outer loop index num1Idx and move the two inner loop indexes inwards as long as num3Idx > num2Idx. Once the condition num3Idx > num2Idx is false we stop the inner loop and increment the outer loop index num1Idx, also update num2Idx and num3Idx, num2Idx=num1Idx+1 and num3Idx=n-1.
Take a variable sum to store the triplet sum. sum = nums[num1Idx] + nums[num2Idx] + nums[num3Idx]. Now there are three possibilities: a. If sum is equal to 0 we add it to our result. b. If sum is greater than 0 we need to decrease the sum value to make it equal to 0, so we decrement num3Idx index. c. If sum is less than 0 we need to increase sum value to make it equal to 0, so we increment num2Idx index.
The inner loop should run as long as num3Idx > num2Idx for each iteration of the outer loop. We return the result once all the triplet combinations are processed.
The above 4 steps ensure that we find all triplets whose sum is equal to 0. But it will also add duplicates to the result array. To skip duplicate triplets we need to add two conditions to our algorithm, one in the outer loop and one in the inner loop. In the outer loop if nums[num1Idx] == nums[num1Idx-1] i.e. if current num1Idx value is same as previous number (num1Idx-1) we skip the current number (we don't have to consider the current number for calculating our result). This condition ensures that we skip all duplicates from the left side of the array. Similarly to skip all numbers from the right side of the array, once we find a triplet with sum equal to zero we keep decrementing num3Idx until nums[num3Idx] != nums[num3Idx +1] (in the inner loop).
Simulation
To make this more clear let us understand this algorithm with a simulation.
Consider you are given the below input array nums of size n = 5:
The first step is to sort the given array. After sorting nums will be:
Iteration 1
For the 1st iteration of the outer loop num1Idx = 0, num2Idx = num1Idx + 1 = 1 and num3Idx = n-1 = 4. Same is show in figure below:
Now we calculate the sum for array elements at current num1Idx, num2Idx and num3Idx.
sum = nums [num1Idx] + nums [num2Idx] + nums [num3Idx]
sum = nums[0] + nums[1] + nums[4] = (-1) + (-1) + 2 = 0
As you can see for the current values of num1Idx, num2Idx and num3Idx sum = 0, so we add it to our result. So result = [[-1, -1, 2]] and also decrement num3Idx. There is no need to make the duplicate check in the inner loop as num3Idx is the last element in the array.
Now the updated values of index variables are num1Idx = 0, num2Idx = 1 and num3Idx = 3.
Again calculate sum,
sum = nums[0] + nums[1] + nums[3] = (-1) + (-1) + 1 = -1.
Sum is less than 0, so we increment num2Idx.
Now sum = nums[0] + nums[2] + nums[3] = (-1) + 0 + 1 = 0. Sum is equal to 0, so we add the current triplet [-1, 0, 1] to the result and decrement num3Idx. Also make the duplicate check in the inner loop, nums[num3Idx ] != nums[num3Idx+1], so there is no possibility of a duplicate for the current value of num3Idx, therefore no need to decrement num3Idx further.
The updated values of index variables are num1Idx = 0, num2Idx = 2 and num3Idx = 2. As you can see num2Idx is equal to num3Idx, so we stop our inner loop and increment the outer loop index num1Idx by 1.
Iteration 2
For the second iteration of the outer loop, the updated values for indexes are num1Idx=1, num2Idx=num1Idx+1=2 and num3Idx= n-1 = 5-1 = 4.
Since the value of num1Idx is same as the previous iteration num1Idx value, we end up with duplicate triplets if consider this value again. Therefore we need to skip the current num1Idx, so increment num1Idx.
Now num1Idx = 2, num2Idx = 3 and num3Idx = 4.
And sum = nums[2] + nums[3] + nums[4] = 0 + 1 + 2 = 3 is greater than 0, so we decrement num3Idx.
Again num2Idx is equal to num3Idx, therefore we stop the inner loop, also we have reached the end of array, so we stop our algorithm and return the result.
Implementation
Language: Go
Language: Java
Language: Python
Complexity Analysis
Time Complexity: O(n^2)
Time complexity is O(n log n) for sorting the input array + O(n^2) since for the two loops. So the overall time complexity is O(n^2).
Space Complexity: O(1)
No extra space is used.
That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you.
If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form).
You can explore more such amazing articles from code recipe here.
Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.
