C++ - Easiest Beginner Friendly Sol || Set + Two Pointer Approach || O(n^3) time and O(n) space
Intuition of this Problem:\nSet is used to prevent duplicate quadruplets and parallely we will use two pointer approach to maintain k and l.\n Describe your fir
# Intuition of this Problem:\nSet is used to prevent duplicate quadruplets and parallely we will use two pointer approach to maintain k and l.\n<!-- Describe your first thoughts on how to solve this problem. -->\n**NOTE - PLEASE READ APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.**\n\n# Approach for this Problem:\n1. Sort the input array of integers nums.\n2. Initialize an empty set s, and an empty 2D vector output.\n3. Use nested loops to iterate through all possible combinations of quadruplets in nums.\n4. For each combination, use two pointers (k and l) to traverse the sub-array between the second and second-to-last elements of the combination.\n5. At each iteration of the innermost while loop, calculate the sum of the current quadruplet and check if it is equal to the target.\n6. If the sum is equal to the target, insert the quadruplet into the set s and increment both pointers (k and l).\n7. If the sum is less than the target, increment the pointer k.\n8. If the sum is greater than the target, decrement the pointer l.\n9. After all quadruplets have been checked, iterate through the set s and add each quadruplet to the output vector.\n10. Return the output vector.\n<!-- Describe your approach to solving the problem. -->\n\n# Humble Request:\n- If my solution is helpful to you then please **UPVOTE** my solution, your **UPVOTE** motivates me to post such kind of solution.\n- Please let me know in comments if there is need to do any improvement in my approach, code....anything.\n- **Let\'s connect on** https://www.linkedin.com/in/abhinash-singh-1b851b188\n\n![57jfh9.jpg](https://assets.leetcode.com/users/images/c2826b72-fb1c-464c-9f95-d9e578abcaf3_1674104075.4732099.jpeg)\n\n# Code:\n```C++ []\n//Optimized Approach using two pointer - O(n^3) time and O(n) space\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int>& nums, int target) {\n        sort(nums.begin(), nums.end());\n        set<vector<int>> s;\n        vector<vector<int>> output;\n        for (int i = 0; i < nums.size(); i++){\n            for(int j = i+1; j < nums.size(); j++){\n                int k = j + 1;\n                int l = nums.size() - 1;\n                while (k < l) {\n                    //by writing below 4 statement this way it will not give runtime error\n                    long long int sum = nums[i];\n                    sum += nums[j];\n                    sum += nums[k];\n                    sum += nums[l];\n                    if (sum == target) {\n                        s.insert({nums[i], nums[j], nums[k], nums[l]});\n                        k++;\n                        l--;\n                    } else if (sum < target) {\n                        k++;\n                    } else {\n                        l--;\n                    }\n                }\n            }\n        }\n        for(auto quadruplets : s)\n            output.push_back(quadruplets);\n        return output;\n    }\n};\n```\n```C++ []\n//Brute force Approach - O(n^4) time and O(n) space\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int>& nums, int target) {\n        sort(nums.begin(), nums.end());\n        set<vector<int>> s;\n        vector<vector<int>> output;\n        for (int i = 0; i < nums.size(); i++){\n            for(int j = i+1; j < nums.size(); j++){\n                for(int k = j+1; k < nums.size(); k++){\n                    for(int l = k+1; l < nums.size(); l++){\n                        vector<int> temp;\n                        if(nums[i] + nums[j] + nums[k] + nums[l] == target){\n                            temp.push_back(nums[i]);\n                            temp.push_back(nums[j]);\n                            temp.push_back(nums[k]);\n                            temp.push_back(nums[l]);\n                            s.insert(temp);\n                        }\n                    }\n                }\n            }\n        }\n        for(auto quadruplets : s)\n            output.push_back(quadruplets);\n        return output;\n    }\n};\n```\n```C++ []\n// this peice of code will give runtime error: signed integer overflow: 2000000000 + 1000000000 cannot be represented in type \'int\' for below test case\nnums = [1000000000,1000000000,1000000000,1000000000]\ntarget = 0\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int>& nums, int target) {\n        sort(nums.begin(), nums.end());\n        set<vector<int>> s;\n        vector<vector<int>> output;\n        for (int i = 0; i < nums.size(); i++){\n            for(int j = i+1; j < nums.size(); j++){\n                int k = j + 1;\n                int l = nums.size() - 1;\n                while (k < l) {\n                    //for below statement it will give runtime error\n                    long long int sum = nums[i] + nums[j] + nums[k] + nums[l];\n                    if (sum == target) {\n                        s.insert({nums[i], nums[j], nums[k], nums[l]});\n                        k++;\n                        l--;\n                    } else if (sum < target) {\n                        k++;\n                    } else {\n                        l--;\n                    }\n                }\n            }\n        }\n        for(auto quadruplets : s)\n            output.push_back(quadruplets);\n        return output;\n    }\n};\n```\n```Java []\nclass Solution {\n    public List<List<Integer>> fourSum(int[] nums, int target) {\n        Arrays.sort(nums);\n        Set<List<Integer>> s = new HashSet<>();\n        List<List<Integer>> output = new ArrayList<>();\n        for (int i = 0; i < nums.length; i++) {\n            for (int j = i + 1; j < nums.length; j++) {\n                int k = j + 1;\n                int l = nums.length - 1;\n                while (k < l) {\n                    long sum = nums[i];\n                    sum += nums[j];\n                    sum += nums[k];\n                    sum += nums[l];\n                    if (sum == target) {\n                        s.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));\n                        k++;\n                        l--;\n                    } else if (sum < target) {\n                        k++;\n                    } else {\n                        l--;\n                    }\n                }\n            }\n        }\n        output.addAll(s);\n        return output;\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n        nums.sort()\n        s = set()\n        output = []\n        for i in range(len(nums)):\n            for j in range(i+1, len(nums)):\n                k = j + 1\n                l = len(nums) - 1\n                while k < l:\n                    sum = nums[i] + nums[j] + nums[k] + nums[l]\n                    if sum == target:\n                        s.add((nums[i], nums[j], nums[k], nums[l]))\n                        k += 1\n                        l -= 1\n                    elif sum < target:\n                        k += 1\n                    else:\n                        l -= 1\n        output = list(s)\n        return output\n\n```\n\n# Time Complexity and Space Complexity:\n- Time complexity: **O(n^3)** // where n is the size of array\n\nThe outer two loops have a time complexity of O(n^2) and the inner while loop has a time complexity of O(n). The total time complexity is therefore O(n^2) * O(n) = O(n^3)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(n)**\n\nThe set s stores all unique quadruplets, which in the worst case scenario is O(n).\nThe output vector stores the final output, which is also O(n).\nThe total space complexity is therefore O(n) + O(n) = O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Two Pointers', 'Python', 'C++', 'Java']