In this guide we will provide 15. 3Sum LeetCode Solution with best time and space complexity. The solution to Sum problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.
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 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.
Constraints:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(|\texttt{ans}|)
15. 3Sum LeetCode Solution in C++
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
if (nums.size() < 3)
return {};
vector<vector<int>> ans;
ranges::sort(nums);
for (int i = 0; i + 2 < nums.size(); ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
// Choose nums[i] as the first number in the triplet, then search the
// remaining numbers in [i + 1, n - 1].
int l = i + 1;
int r = nums.size() - 1;
while (l < r) {
const int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
ans.push_back({nums[i], nums[l++], nums[r--]});
while (l < r && nums[l] == nums[l - 1])
++l;
while (l < r && nums[r] == nums[r + 1])
--r;
} else if (sum < 0) {
++l;
} else {
--r;
}
}
}
return ans;
}
}; /* code provided by PROGIEZ */
15. 3Sum LeetCode Solution in Java
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if (nums.length < 3)
return new ArrayList<>();
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i + 2 < nums.length; ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
// Choose nums[i] as the first number in the triplet, then search the
// remaining numbers in [i + 1, n - 1].
int l = i + 1;
int r = nums.length - 1;
while (l < r) {
final int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
ans.add(Arrays.asList(nums[i], nums[l++], nums[r--]));
while (l < r && nums[l] == nums[l - 1])
++l;
while (l < r && nums[r] == nums[r + 1])
--r;
} else if (sum < 0) {
++l;
} else {
--r;
}
}
}
return ans;
}
} // code provided by PROGIEZ
15. 3Sum LeetCode Solution in Python
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
if len(nums) < 3:
return []
ans = []
nums.sort()
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
# Choose nums[i] as the first number in the triplet, then search the
# remaining numbers in [i + 1, n - 1].
l = i + 1
r = len(nums) - 1
while l < r:
summ = nums[i] + nums[l] + nums[r]
if summ == 0:
ans.append((nums[i], nums[l], nums[r]))
l += 1
r -= 1
while nums[l] == nums[l - 1] and l < r:
l += 1
while nums[r] == nums[r + 1] and l < r:
r -= 1
elif summ < 0:
l += 1
else:
r -= 1
return ans #code by PROGIEZ
