3 Sum - Leetcode #15 Short & Simple Solution
Updated: Jan 14
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.
Problem Statement
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 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 indices 0, 2, 3 and 1, 2, 3 in our final result.
The most simple and straight forward solution to this problem is to use the brute force approach. In brute force approach we find every possible triplet from the given array, check if its sum is equal to zero and return the result (ensuring there are no duplicate triplets in the result). However, the time complexity of this solution is O(n^3) as we have to run 3 nested loops in order to implement this.
Three Pointer Approach
We can use a variation of the two pointer technique to solve this problem with a better time complexity compared to the brute force approach. The idea is to sort the array, use three pointer variables tp 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 as we traverse the array, if we use two pointers from left and right, we can easily avoid duplicate triplets.
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. During our processing, if we consider all of these duplicate elements, it would result in duplicate triplets like [-3, -2, 5] and [-3, -2, 5]. We can 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.
Algorithm
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.
Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:
Code
Go Solution
Python Solution
Java Solution
JavaScript Solution
TypeScript Solution
C++ Solution
C# Solution
C Solution
PHP Solution
Kotlin Solution
Swift Solution
Ruby Solution
Scala Solution
Rust Solution
Dart Solution
Erlang Solution
Complexity Analysis
Time Complexity
Sorting the array:
If n is the size of nums array, sorting the nums array takes O(n log n).
Outer Loop (num1Idx):
The outer loop runs from index 0 to n-2. So it iterates O(n) times.
Inner Loop (num2Idx and num3Idx):
For each iteration of the outer loop num1Idx, the inner loop iterates through the rest of the nums array elements using num2Idx and num3Idx indices. In the worst case this can make n iterations. As num1Idx increases the inner loop has to process lesser and lesser elements with each iteration. However the time complexity for this nested loop combination is O(n^2).
Overall Time Complexity:
Considering the above analysis, the overall time complexity of this algorithm is O(n log n) + O(n^2) = O(n^2).
Space Complexity
The algorithm uses constant space variable for its operations, so if we don't consider the result variable the space complexity is O(1).
If we consider the result variable, the space complexity is O(n^2) in the worst case when every triplet in nums array sums to zero.
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.
I appreciate time and effort you put into writing this article. Separate colours, visualisation of indices helps greatly. Keep up the good work!
Thanks for the fully detailed solution. Please tell me difference between these lines of code.
List < List < Integer >> result = new ArrayList < > ();
List < List < Integer >> result = new ArrayList < List < Integer >> ();
Why we write List on LHS and arraylist on RHS? If we had written ArrayList on both sides what difference will it make?
Also, another optimization can be done to break the outer loop if nums[num1Idx]>0.
there should be atleast one negative or zero in the triplets
I think we can optimize further In step 6: "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. ..."
You are skipping right pointer until nums[num3Idx] != nums[num3Idx +1].
We can skip the inner left pointer too until nums[num2Idx] != nums[num2Idx +1].
There's a mistake in the explanation of the 2nd solution. In step 4 of your algorithm you said at the end " If sum is less than 0 we need to increase sum value to make it equal to 0, so we increment num1Idx index." I think you meant increment num2Idx? Well written post overall!