LeetCode #15 - 3 Sum
November 10, 2020
Hello fellow LeetCode enthusiasts 👋! Today we are going to discuss one of the popular problems on LeetCode.
Problem Statement
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.
Notice that the solution set must not contain duplicate triplets.
Constraints:
- 0 ≤
nums.length≤ 3000 - -105 ≤
nums[i]≤ 105
Examples
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]Example 2:
Input: nums = []
Output: []Example 3:
Input: nums = [0]
Output: []Analysis
This problem is an extension of the Two Sum problem. Here, the target is zero. Thus, if a + b + c = 0, then a + b = -c. This essentially reduces this problem to Two Sum.
Thus, we have to find such triplets whose sum is zero and there should be no duplicates in the answer.
Approach
The naive approach is to check for each possible triplet. This can be done via three nested loops which will make the time complexity proportional to the third power of the number of elements in the array i.e., O(n3).
Can we do better 🤔? We can use two pointer trick as follows -
- Sort the array (in time O(n * log(n))).
- Now for each element
i, do the following steps - Set two pointers left —
j = i + 1and right —k = nums.length - 1. - Check if
nums[i] + nums[j] + nums[k] == 0and if it is zero, add these three numbers to the resultant list. - If the sum
nums[i] + nums[j] + nums[k] < 0, this means we can move left pointer forward because since the array is sorted and the sum is less than zero, therefore, it makes sense to check for greater value to make the sum bigger. - If the sum
nums[i] + nums[j] + nums[k] > 0, this means we are too right and can move the right pointer backward because since the array is sorted and the sum is greater than zero, therefore, it makes sense to check for smaller value to make the sum lesser. - In between loops, we also need to make sure that we are not checking for duplicate values.
Time Complexity
We are scanning the entire array keeping one element fixed. We are doing this for every element in the array. Thus, we are scanning each element of array n number of times. And we are doing this for n times, hence the worst case time complexity will be O(n2 + n * log n) which comes down to O(n2).
Space Complexity
We are not using any data structure for the intermediate computations, hence the space complexity is O(1).
Code
Java
public class ThreeSum {
public List<List<Integer>> threeSum(int[] nums) {
// Sort the array
Arrays.sort(nums);
// Length of the array
int n = nums.length;
// Resultant list
List<List<Integer>> triplets = new ArrayList<>();
// Loop for each element of the array
for (int i = 0; i < n; i++) {
// Skip the duplicates
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// Left and right pointers
int j = i + 1;
int k = n - 1;
// Loop for all the remaining pairs
while (j < k) {
if (nums[i] + nums[j] + nums[k] == 0) {
triplets.add(Arrays.asList(nums[i], nums[j], nums[k]));
j++;
// Never let j refer to the same value twice (in an output) to avoid duplicates
while (j < k && nums[j] == nums[j - 1]) {
j++;
}
} else if (nums[i] + nums[j] + nums[k] < 0) {
j++;
} else {
k--;
}
}
}
return triplets;
}
}Python
"""
@author - Anirudh Sharma
"""
def threeSum(nums: List[int]) -> List[List[int]]:
# Sort the given array
nums.sort()
# Length of the array
n = len(nums)
# Resultant list
triplets = list()
# Loop for each character in the array
for i in range(0, n):
# Avoid duplicates due to i
if i > 0 and nums[i] == nums[i - 1]:
continue
# Left and right pointers
j = i + 1
k = n - 1
# Loop for remaining pairs
while j < k:
if nums[i] + nums[j] + nums[k] == 0:
triplets.append([nums[i], nums[j], nums[k]])
j += 1
# Avoid duplicates for j
while j < k and nums[j] == nums[j - 1]:
j += 1
elif nums[i] + nums[j] + nums[k] < 0:
j += 1
else:
k -= 1
return tripletsJavaScript
var threeSum = function (nums) {
// Sort the array
nums.sort((a, b) => a - b);
// Length of the array
const n = nums.length;
// Resultant list
const triplets = [];
// Loop for each element of the array
for (let i = 0; i < n; i++) {
// Skip the duplicates
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
// Left and right pointers
let j = i + 1;
let k = n - 1;
// Loop for all the remaining pairs
while (j < k) {
if (nums[i] + nums[j] + nums[k] === 0) {
triplets.push([nums[i], nums[j], nums[k]]);
j++;
// Never let j refer to the same value twice (in an output) to avoid duplicates
while (j < k && nums[j] === nums[j - 1]) {
j++;
}
} else if (nums[i] + nums[j] + nums[k] < 0) {
j++;
} else {
k--;
}
}
}
return triplets;
};Kotlin
fun threeSum(nums: IntArray): List<List<Int>> {
// Sort the array
Arrays.sort(nums)
// Length of the array
val n = nums.size
// Resultant list
val triplets: MutableList<List<Int>> = ArrayList()
// Loop for each element of the array
for (i in 0 until n) {
// Skip the duplicates
if (i > 0 && nums[i] == nums[i - 1]) {
continue
}
// Left and right pointers
var j = i + 1
var k = n - 1
// Loop for all the remaining pairs
while (j < k) {
when {
nums[i] + nums[j] + nums[k] == 0 -> {
triplets.add(listOf(nums[i], nums[j], nums[k]))
j++
// Never let j refer to the same value twice (in an output) to avoid duplicates
while (j < k && nums[j] == nums[j - 1]) {
j++
}
}
nums[i] + nums[j] + nums[k] < 0 -> {
j++
}
else -> {
k--
}
}
}
}
return triplets
}Complete Code
Conclusion
Congratulations 👏! We have solved one more problem from LeetCode.
I hope you enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork 🔪 and star ⭐ it.
Till next time… Happy coding 😄 and Namaste 🙏!
