Beats 💯 percent Java, Python,C++ with full explanation of code
Intuition\nThis code solves the 4-sum problem, where the goal is to find all unique quadruplets in a list of numbers that add up to a given target. Here\u2019s 
# Intuition\nThis code solves the 4-sum problem, where the goal is to find all unique quadruplets in a list of numbers that add up to a given target. Here\u2019s the step-by-step intuition behind the approach:\n\n# **1. Sort the Array**\n\nSorting the array simplifies the process of finding and skipping duplicates, as well as enables efficient two-pointer traversal to explore possible sums. After sorting, similar numbers are grouped together, making it easier to skip duplicates by comparing adjacent elements.\n\n# **2. Fix Two Elements with Nested Loops (Outer Two Loops)**\n\nThe idea is to break down the problem into smaller parts. By fixing the first two elements in a quadruplet (nums[i] and nums[j]), we transform the 4-sum problem into a simpler 2-sum problem for the remaining two elements (nums[li] and nums[ri]).\n\nLoop over i: The first loop iterates over the array to fix the first element of the quadruplet (nums[i]). If nums[i] is the same as nums[i - 1], it skips this index to avoid duplicate quadruplets.\n\n\nLoop over j: The second loop, starting after i, fixes the second element of the quadruplet (nums[j]). Similarly, it skips duplicates to avoid repeating quadruplets with the same first two elements.\n\n# **3. Use a Two-Pointer Technique for the Remaining Two Elements**\n\nOnce nums[i] and nums[j] are fixed, we use two pointers (li and ri) to find pairs of elements (nums[li] and nums[ri]) that complete the quadruplet to reach the target sum.\n\n\t\u2022\tCalculate the Sum: sum = nums[i] + nums[j] + nums[li] + nums[ri].\n\t\u2022\tCompare with the Target:\n\t\u2022\tIf sum == target: The quadruplet [nums[i], nums[j], nums[li], nums[ri]] is a valid solution, so it\u2019s added to the result list.\n\t\u2022\tIf sum < target: To increase the sum, move the left pointer li one step right.\n\t\u2022\tIf sum > target: To decrease the sum, move the right pointer ri one step left.\n\n# **4. Skip Duplicates with Two Pointers**\n\nAfter finding a valid quadruplet, the code increments li and decrements ri while skipping any duplicates (i.e., if the next element at li or ri is the same as the previous one). This avoids repeating quadruplets with the same third and fourth elements.\n\n# **5. Return the Result**\n\nAfter all loops and pointer movements, the list ans contains all unique quadruplets that sum up to the target.\n\nWhy This Approach Works Efficiently\n\n\t\u2022\tReduced Complexity: By reducing the 4-sum problem to a 2-sum problem using nested loops and two pointers, we keep the solution efficient. Sorting and using two-pointer traversal within a sorted array allows skipping duplicate quadruplets in an orderly way.\n\t\u2022\tAvoids Duplicates: Skipping duplicate elements ensures each quadruplet is unique, reducing unnecessary computations and maintaining optimal performance.\n\n\n# Complexity\n- Time complexity:\n\t1.\tSorting the Array: Sorting nums takes O(n \\log n), where n is the length of the array.\n\t2.\tNested Loops for Fixing the First Two Elements:\n\t\u2022\tThe outer two loops iterate over the array with indices i and j.\n\t\u2022\tFor each fixed pair (i, j), a two-pointer search is performed for the remaining two elements (li and ri).\n\t3.\tTwo-Pointer Search:\n\t\u2022\tFor each pair (i, j), the two-pointer search from li to ri has a time complexity of O(n).\n\t\u2022\tSo, for each pair (i, j), finding pairs with two pointers takes O(n).\n\nPutting it all together:\n\n\t\u2022\tThe two outer loops with indices i and j contribute O(n^2).\n\t\u2022\tThe two-pointer search for each (i, j) combination is O(n).\n\nThus, the total time complexity is:\n\n*# O(n^2 . n) = **O(n^3)***\n\n\n- Space complexity:\n O(n^2)\n\n# Code\n```java []\nclass Solution {\n    public List<List<Integer>> fourSum(int[] nums, int target) {\n        List<List<Integer>> ans= new ArrayList<>();\n        int n = nums.length;\n\n        Arrays.sort(nums);\n\n        for(int i=0;i<n-3;i++){\n\n            if(i > 0 && nums[i-1] == nums[i])\n                continue;\n\n            for(int j =i+1;j<n-2;j++){\n\n                if(j > i+1 && nums[j-1] == nums[j])\n                    continue;\n                int li = j+1;\n                int ri = n-1;\n\n                while(li<ri){\n                    long sum = nums[i]+nums[j];\n                    sum += nums[li]+nums[ri];\n\n                    if(sum == target){\n                        ans.add(Arrays.asList(nums[i],nums[j],nums[li],nums[ri]));\n\n                        li++;\n                        ri--;\n\n                        while(li < ri && nums[li-1] == nums[li])li++;\n\n                        while(li<ri && nums[ri+1] == nums[ri]) ri--;\n                    } else if(sum < target){\n                        li++;\n                    }else{\n                        ri--;\n                    }\n                }\n            }\n        }\n        return ans;\n    }\n}\n```\n```python []\nclass Solution(object):\n    def fourSum(self, nums, target):\n        ans = []\n        n = len(nums)\n\n        nums.sort()\n\n        for i in range(n - 3):\n            if i > 0 and nums[i] == nums[i - 1]:\n                continue\n\n            for j in range(i + 1, n - 2):\n                if j > i + 1 and nums[j] == nums[j - 1]:\n                    continue\n\n                li, ri = j + 1, n - 1\n\n                while li < ri:\n                    total = nums[i] + nums[j] + nums[li] + nums[ri]\n\n                    if total == target:\n                        ans.append([nums[i], nums[j], nums[li], nums[ri]])\n\n                        li += 1\n                        ri -= 1\n\n                        while li < ri and nums[li] == nums[li - 1]:\n                            li += 1\n                        while li < ri and nums[ri] == nums[ri + 1]:\n                            ri -= 1\n                    elif total < target:\n                        li += 1\n                    else:\n                        ri -= 1\n\n        return ans\n```\n```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int>& nums, int target) {\n        std::vector<std::vector<int>> ans;\n        int n = nums.size();\n\n        std::sort(nums.begin(), nums.end());\n\n        for (int i = 0; i < n - 3; i++) {\n            if (i > 0 && nums[i] == nums[i - 1]) continue;\n\n            for (int j = i + 1; j < n - 2; j++) {\n                if (j > i + 1 && nums[j] == nums[j - 1]) continue;\n\n                int li = j + 1;\n                int ri = n - 1;\n\n                while (li < ri) {\n                    long long sum = static_cast<long long>(nums[i]) + nums[j] + nums[li] + nums[ri];\n\n                    if (sum == target) {\n                        ans.push_back({nums[i], nums[j], nums[li], nums[ri]});\n                        li++;\n                        ri--;\n\n                        while (li < ri && nums[li] == nums[li - 1]) li++;\n                        while (li < ri && nums[ri] == nums[ri + 1]) ri--;\n                    } else if (sum < target) {\n                        li++;\n                    } else {\n                        ri--;\n                    }\n                }\n            }\n        }\n\n        return ans;\n    }\n};\n```\n![Gemini_Generated_Image_8wyq3d8wyq3d8wyq.jpeg](https://assets.leetcode.com/users/images/472a37a3-064b-4423-b946-ce0452842f05_1730009382.8325167.jpeg)\n
['Python', 'C++', 'Java']