3Sum LeetCode Solution

Here, We see 3Sum problem Solution. This Leetcode problem done in many programming language like C++, Java, JavaScript, Python etc. with different approach.

3Sum LeetCode Solution

3Sum LeetCode Solution

Problem Statement ->

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.

3Sum C++ Solution ->

class Solution { public: vector<vector<int> > threeSum(vector<int> &num) { vector<vector<int> > result; std::sort(num.begin(), num.end()); for (int i = 0; i < num.size(); i++) { int target = -num[i]; int front = i + 1; int back = num.size() - 1; while (front < back) { int sum = num[front] + num[back]; // Finding answer which start from number num[i] if (sum < target) front++; else if (sum > target) back--; else { vector<int> triplet = {num[i], num[front], num[back]}; result.push_back(triplet); // Processing duplicates of Number 2 // Rolling the front pointer to the next different number forwards while (front < back && num[front] == triplet[1]) front++; // Processing duplicates of Number 3 // Rolling the back pointer to the next different number backwards while (front < back && num[back] == triplet[2]) back--; } } // Processing duplicates of Number 1 while (i + 1 < num.size() && num[i + 1] == num[i]) i++; } return result; } };
Code language: C++ (cpp)

3Sum Java Solution ->

public class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); if(nums.length < 3) return result; Arrays.sort(nums); int i = 0; while(i < nums.length - 2) { if(nums[i] > 0) break; int j = i + 1; int k = nums.length - 1; while(j < k) { int sum = nums[i] + nums[j] + nums[k]; if(sum == 0) result.add(Arrays.asList(nums[i], nums[j], nums[k])); if(sum <= 0) while(nums[j] == nums[++j] && j < k); if(sum >= 0) while(nums[k--] == nums[k] && j < k); } while(nums[i] == nums[++i] && i < nums.length - 2); } return result; } }
Code language: Java (java)

3Sum JavaScript Solution ->

var threeSum = function(nums) { var result = []; if (nums.length < 3) { return result; } nums = nums.sort(function(a, b) { return a - b; }); for (var i = 0; i < nums.length - 2; i++) { if (nums[i] > 0) { return result; } if (i > 0 && nums[i] == nums[i - 1]) { continue; } for (var j = i + 1, k = nums.length - 1; j < k;) { if (nums[i] + nums[j] + nums[k] === 0) { result.push([nums[i], nums[j], nums[k]]); j++; k--; while (j < k && nums[j] == nums[j - 1]) { j++; } while (j < k && nums[k] == nums[k + 1]) { k--; } } else if (nums[i] + nums[j] + nums[k] > 0) { k--; } else { j++; } } } return result; };
Code language: JavaScript (javascript)

3Sum Python Solution ->

class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: ans = set([]) plus = sorted([n for n in nums if n>0]) plus_c = set(plus) zero = [n for n in nums if n == 0] minus = sorted([n for n in nums if n<0]) minus_c = set(minus) # all zero if len(zero)>2: ans.add((0,0,0)) # plus zero minus if len(zero)>0: for n in minus: if -n in plus_c: ans.add((n,0,-n)) # plus minus minus n = len(minus) for i in range(n): for j in range(i+1,n): diff = -(minus[i]+minus[j]) if diff in plus_c: ans.add((minus[i],minus[j],diff)) # plus plus minus n = len(plus) for i in range(n): for j in range(i+1,n): diff = -(plus[i]+plus[j]) if diff in minus_c: ans.add((diff,plus[i],plus[j])) return list(ans)
Code language: Python (python)

Leave a Comment

Your email address will not be published. Required fields are marked *