15. 3Sum

Leetcode

📝 Problem Details

• Title: 15. 3Sum
• Link: https://leetcode.com/problems/3sum/
• Difficulty: Medium
• Tags/Categories: Hashmap Two-Pointers

💭What Were My Initial Thoughts?

- i know how to solve 2 sum, how can i extend that to solve this problem
- 2 sum involves inserting each element into an unordered set, calculating the complement with the target and current element
	- check if the complement exists and return true if it exists
- in this case target is fixed to be zero
- there can also be multiple results/combinations of elements

🤔What Did I Struggle With?

~

💡 Explanation of Solution

1. sort the input array
2. create 3 pointers i,j,k , 1 being fixed in a for loop (i)
3. use the sum of the tree pointers so store triplets
4. increase and decrease pointers j and k based on the result of sum

⌛ Complexity Analysis

Time Complexity: O(n log n) 
- where we are bound by the initial sorting of the array

Space Complexity: O(n)
- the hashset used to store unique triplets

💻 Implementation of Solution

class Solution {
 
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int target = 0;
        sort(nums.begin(), nums.end());
        set<vector<int>> set;
 
        for(int i=0; i < nums.size(); i++) {
            int j = i + 1;
            int k = nums.size()-1;
       
            while( j < k) { //possible change this to <=
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == target) {
                    set.insert({nums[i], nums[j], nums[k]});
                    j++;
                    k--;
                }
                else if(sum < target) j++;
                else k--;
            }
        }
            vector<vector<int>> result;
 
            for(auto triplets : set) {
                result.push_back(triplets);
            }
 
            return result;
    }
};