3 SUM
Find triplet that add upto zero
1)Nested loops TC o(n³)
2)Hashset TC o(n²) SC o(n)
3)Two pointer TC o(nlogn)+o(n²)
3 Approach most efficient one
Lets revise some concepts.
Get suhama’s stories in your inbox
Join Medium for free to get updates from this writer.
Two pointers find pairs of numbers to get third.Sorting array sort to facilitate 2 pointer technique.Avoid duplicates only unique triplets are returned
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res; // To store the result triplets
sort(nums.begin(), nums.end()); // Sort the array
for (int i = 0; i < nums.size(); i++) {
// Skip duplicate elements
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
int j = i + 1; // Left pointer
int k = nums.size() — 1; // Right pointer
while (j < k) {
int total = nums[i] + nums[j] + nums[k]; // Calculate the sum
if (total > 0) {
k — ; // Decrease the right pointer
} else if (total < 0) {
j++; // Increase the left pointer
} else {
res.push_back({nums[i], nums[j], nums[k]}); // Found a triplet
j++; // Move the left pointer
// Skip duplicates for the left pointer
while (nums[j] == nums[j-1] && j < k) {
j++;
}
}
}
}
return res; // Return the result
}
};
Suhama Mustafa
