C++/Java/Python/JavaScript || 🚀 ✅ Two Pointer || 🚀 ✅Array
Intuition:\nThe problem asks to find all unique quadruplets in the given array whose sum equals the target value. We can use a similar approach as we do for the
# Intuition:\nThe problem asks to find all unique quadruplets in the given array whose sum equals the target value. We can use a similar approach as we do for the 3Sum problem. We can sort the array and then use two pointers approach to find the quadruplets whose sum equals the target value.\n\n# Approach:\n\n1. Sort the input array in non-decreasing order.\n2. Traverse the array from 0 to n-3 and use a variable i to keep track of the first element in the quadruplet.\n3. If the current element is the same as the previous element, skip it to avoid duplicates.\n4. Traverse the array from i+1 to n-2 and use a variable j to keep track of the second element in the quadruplet.\n5. If the current element is the same as the previous element, skip it to avoid duplicates.\n6. Use two pointers, left = j+1 and right = n-1, to find the other two elements in the quadruplet whose sum equals the target value.\n7. If the sum of the four elements is less than the target value, increment left pointer.\n8. If the sum of the four elements is greater than the target value, decrement right pointer.\n9. If the sum of the four elements is equal to the target value, add the quadruplet to the result and increment left and decrement right pointers.\n10. Skip duplicate values of left and right pointers to avoid duplicate quadruplets.\n11. Return the result.\n\n# Complexity\n- Time Complexity: O(n^3) where n is the length of the input array. The two outer loops run in O(n^2) time and the inner two-pointer loop runs in O(n) time.\n\n- Space Complexity: O(1) because we are not using any extra space apart from the output array.\n- \n# Similar Question: [https://leetcode.com/problems/3sum/solutions/3416585/c-java-python-javascript-fully-explained-two-pointer-array/?orderBy=most_votes]()\n---\n# C++\n```\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int>& nums, int target) {\n        vector<vector<int>> quadruplets;\n        int n = nums.size();\n        // Sorting the array\n        sort(nums.begin(), nums.end());\n        for (int i = 0; i < n - 3; i++) {\n            // Skip duplicates\n            if (i > 0 && nums[i] == nums[i - 1]){\n                continue;\n            }\n            for (int j = i + 1; j < n - 2; j++) {\n                // Skip duplicates\n                if (j > i + 1 && nums[j] == nums[j - 1]){\n                    continue;\n                }\n                int left = j + 1;\n                int right = n - 1;\n                while (left < right) {\n                    long long sum = static_cast<long long>(nums[i]) + nums[j] + nums[left] + nums[right];\n                    if (sum < target) {\n                        left++;\n                    } else if (sum > target) {\n                        right--;\n                    } else {\n                        quadruplets.push_back({nums[i], nums[j], nums[left], nums[right]});\n                        // Skip duplicates\n                        while (left < right && nums[left] == nums[left + 1]){\n                            left++;\n                        }\n                        while (left < right && nums[right] == nums[right - 1]){\n                            right--;\n                        }\n                        left++;\n                        right--;\n                    }\n                }\n            }\n        }\n        return quadruplets;\n    }\n};\n```\n---\n# Python\n```\nclass Solution(object):\n    def fourSum(self, nums, target):\n        quadruplets = []\n        n = len(nums)\n        # Sorting the array\n        nums.sort()\n        for i in range(n - 3):\n            # Skip duplicates\n            if i > 0 and nums[i] == nums[i - 1]:\n                continue\n            for j in range(i + 1, n - 2):\n                # Skip duplicates\n                if j > i + 1 and nums[j] == nums[j - 1]:\n                    continue\n                left = j + 1\n                right = n - 1\n                while left < right:\n                    sum = nums[i] + nums[j] + nums[left] + nums[right]\n                    if sum < target:\n                        left += 1\n                    elif sum > target:\n                        right -= 1\n                    else:\n                        quadruplets.append([nums[i], nums[j], nums[left], nums[right]])\n                        # Skip duplicates\n                        while left < right and nums[left] == nums[left + 1]:\n                            left += 1\n                        while left < right and nums[right] == nums[right - 1]:\n                            right -= 1\n                        left += 1\n                        right -= 1\n        return quadruplets\n\n```\n\n---\n# JAVA\n```\nclass Solution {\n    public List<List<Integer>> fourSum(int[] nums, int target) {\n        List<List<Integer>> quadruplets = new ArrayList<>();\n        int n = nums.length;\n        // Sorting the array\n        Arrays.sort(nums);\n        for (int i = 0; i < n - 3; i++) {\n            // Skip duplicates\n            if (i > 0 && nums[i] == nums[i - 1]) {\n                continue;\n            }\n            for (int j = i + 1; j < n - 2; j++) {\n                // Skip duplicates\n                if (j > i + 1 && nums[j] == nums[j - 1]) {\n                    continue;\n                }\n                int left = j + 1;\n                int right = n - 1;\n                while (left < right) {\n                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];\n                    if (sum < target) {\n                        left++;\n                    } else if (sum > target) {\n                        right--;\n                    } else {\n                        quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));\n                        // Skip duplicates\n                        while (left < right && nums[left] == nums[left + 1]) {\n                            left++;\n                        }\n                        while (left < right && nums[right] == nums[right - 1]) {\n                            right--;\n                        }\n                        left++;\n                        right--;\n                    }\n                }\n            }\n        }\n        return quadruplets;\n    }\n}\n\n```\n\n---\n# JavaScript\n```\nvar fourSum = function(nums, target) {\n  nums.sort((a, b) => a - b);\n  const quadruplets = [];\n  const n = nums.length;\n  for (let i = 0; i < n - 3; i++) {\n    if (i > 0 && nums[i] === nums[i - 1]) {\n      continue;\n    }\n    for (let j = i + 1; j < n - 2; j++) {\n      if (j > i + 1 && nums[j] === nums[j - 1]) {\n        continue;\n      }\n      let left = j + 1;\n      let right = n - 1;\n      while (left < right) {\n        const sum = BigInt(nums[i]) + BigInt(nums[j]) + BigInt(nums[left]) + BigInt(nums[right]);\n        if (sum < target) {\n          left++;\n        } else if (sum > target) {\n          right--;\n        } else {\n          quadruplets.push([nums[i], nums[j], nums[left], nums[right]]);\n          while (left < right && nums[left] === nums[left + 1]) {\n            left++;\n          }\n          while (left < right && nums[right] === nums[right - 1]) {\n            right--;\n          }\n          left++;\n          right--;\n        }\n      }\n    }\n  }\n  return quadruplets;\n};\n```\n\n---\n\n# Similar Question: [https://leetcode.com/problems/3sum/solutions/3416585/c-java-python-javascript-fully-explained-two-pointer-array/?orderBy=most_votes]()
['Two Pointers', 'Python', 'C++', 'Java', 'JavaScript']