All suggestions are welcome. Please upvote if you like it. Thank you.
Leetcode Problem Link: 15. 3Sum
Brute Force Solution:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
// Brute Force Solution Time O(N^3) & Auxiliary Space O(1)
int len=nums.size();
if(len==0 || len<3) // Atleast three elemnets needed for a triplet
return {};
set<vector<int>> s; // Set stores unique elements only(duplicate triplets not added)
sort(nums.begin(),nums.end());
// Compare all cases of group of three elements for their sum=0 in O(N^3) time
for(int i=0;i<len-2;i++){
for(int j=i+1;j<len-1;j++){
for(int k=j+1;k<len;k++){
if(nums[i]+nums[j]+nums[k]==0){
s.insert({nums[i],nums[j],nums[k]});
}
}
}
}
// Insert all unique triplets in result vector
vector<vector<int>> ans(s.begin(),s.end());
return ans;
}
};
Efficient Solution:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums){
// Optimal Solution Time O(N^2) & Auxiliary Space O(1)
// Two Pointer Algorithm
int len=nums.size();
vector<vector<int>> res;
if(len<3)
return res;
sort(nums.begin(),nums.end());
for(int i = 0; i<len; i++){
if(i>0 && nums[i]==nums[i-1])
// Skip the duplicate elements by incrementing the i index.
// 'continue' terminates current iteration and
// begins next iteration of for loop
continue;
// Keeping nums[i] same, check for sum of triplets=0
// from i+1 till the end of nums vector
int left = i + 1, right = nums.size() - 1;
while(left<right)
{
if(nums[i] + nums[left] + nums[right] == 0){
res.push_back(vector<int>{nums[i],nums[left],nums[right]});
// To skip duplicate elements at left pointer
while(left<right && nums[left]==nums[left+1])
left++;
// To skip duplicate elements at left pointer
while(left<right && nums[right]==nums[right-1])
right--;
// One unique triplet has been found.
// Increment left & decrement right for
// next triplet to be unique
left++;
right--;
}
// Since nums is sorted, so left will be smallest in
// [nums[left],nums[right]] interval and if triplet sum<0,
// then incrementing left will increase the sum
else if(nums[i]+nums[left]+nums[right]<0)
left++;
// Since nums is sorted, so right will be largest in
// [nums[left],nums[right]] interval and if triplet sum>0,
// then decrementing right will decrease the sum
else
right--;
}
}
return res;
}
};
All suggestions are welcome. Please upvote if you like it. Thank you.
Top comments (0)