Most optimal solution with explanation using two pointers approach | C++ and JAVA code
\n\n# Approach\n- Sort the input array nums in ascending order. Sorting the array helps in identifying unique quadruplets and allows us to use the two-pointer a
\n\n# Approach\n- Sort the input array nums in ascending order. Sorting the array helps in identifying unique quadruplets and allows us to use the two-pointer approach efficiently.\n\n- Iterate through each element in the array using a loop variable i from 0 to the second-to-last index.\n\n- Inside the first loop, check if the current element nums[i] is the same as the previous element nums[i-1]. If they are the same, it means we have already considered this element and generated quadruplets for it. In such cases, we continue to the next iteration to avoid duplicates.\n\n- Start a second loop with a variable j from i+1 to the last index. This loop represents the second element in the quadruplet.\n\n- Similar to step 3, check if the current element nums[j] is the same as the previous element nums[j-1]. If they are the same, continue to the next iteration to avoid duplicates.\n\n- Set two pointers k and l. k starts from j+1 (the next element after j) and moves forward, and l starts from the last index of the array and moves backward.\n\n- Enter a while loop where k is less than l. This loop iterates until k and l cross each other.\n\n- Calculate the sum of the current elements: nums[i] + nums[j] + nums[k] + nums[l].\n\n- If the sum is equal to the target, we have found a valid quadruplet. Create a temporary vector temp and store the elements nums[i], nums[j], nums[k], and nums[l] in it. Add this vector to the ans vector, which stores all the unique quadruplets.\n\n- Move the pointers k and l towards each other. Increment k and decrement l.\n\n- Check for any duplicate elements while moving the pointers. If the next element is the same as the previous one, increment k or decrement l until you find a different element. This step helps in avoiding duplicate quadruplets.\n\n- If the sum is greater than the target, decrement l to decrease the sum.\n\n- If the sum is less than the target, increment k to increase the sum.\n\n- After the second loop ends, continue to the next iteration of the first loop.\n\n- Finally, return the ans vector containing all the unique quadruplets.\n\n# Complexity\n- Time complexity:\nO(n^3)\n\n- Space complexity:\nO(1), O(n) to store the answer\n\n# C++ Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int>& nums, int target) {\n        vector<vector<int>> ans;\n        sort(nums.begin(), nums.end());\n        for(int i = 0; i< nums.size(); i++){\n            if(i>0 && nums[i] == nums[i-1]) continue;\n            for(int j = i+1; j< nums.size(); j++){\n                if(j> i+1 && nums[j] == nums[j-1]) continue;\n                int k = j+1;\n                int l = nums.size() - 1;\n                while(k<l){\n                    long long sum = nums[i];\n                    sum += nums[j];\n                    sum += nums[k];\n                    sum += nums[l];\n                    if(sum == target){\n                        vector <int> temp = {nums[i], nums[j], nums[k], nums[l]};\n                        ans.push_back(temp);\n                        k++;\n                        l--;\n                        while(k<l && nums[k] == nums[k-1]) k++;\n                        while(k<l && nums[l] == nums[l+1]) l--;\n                    }\n                    else if(sum > target) l--;\n                    else k++;\n                }\n            }\n        }\n        return ans;\n    }\n};\n```\n# JAVA Code\n```\nclass Solution {\n    public List<List<Integer>> fourSum(int[] nums, int target) {\n        List<List<Integer>> ans = new ArrayList<>();\n        Arrays.sort(nums);\n        \n        for (int i = 0; i < nums.length - 3; i++) {\n            if (i > 0 && nums[i] == nums[i - 1]) {\n                continue;\n            }\n            \n            for (int j = i + 1; j < nums.length - 2; j++) {\n                if (j > i + 1 && nums[j] == nums[j - 1]) {\n                    continue;\n                }\n                \n                int k = j + 1;\n                int l = nums.length - 1;\n                \n                while (k < l) {\n                    long sum = (long) nums[i] + nums[j] + nums[k] + nums[l];\n                    \n                    if (sum == target) {\n                        List<Integer> temp = new ArrayList<>();\n                        temp.add(nums[i]);\n                        temp.add(nums[j]);\n                        temp.add(nums[k]);\n                        temp.add(nums[l]);\n                        ans.add(temp);\n                        \n                        k++;\n                        l--;\n                        \n                        while (k < l && nums[k] == nums[k - 1]) {\n                            k++;\n                        }\n                        \n                        while (k < l && nums[l] == nums[l + 1]) {\n                            l--;\n                        }\n                    } else if (sum < target) {\n                        k++;\n                    } else {\n                        l--;\n                    }\n                }\n            }\n        }\n        \n        return ans;\n    }\n}\n```
['Array', 'Two Pointers', 'Sorting', 'C++', 'Java']