Optimal Solution for 4Sum Problem Using Two-Pointer Technique and Early Exits
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is an extension of the classic two-sum and three-sum problems. Since we\'re
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is an extension of the classic two-sum and three-sum problems. Since we\'re looking for quadruplets, we can use a combination of sorting and the two-pointer technique to reduce the problem\'s complexity. Sorting helps in easily skipping duplicates and narrowing down the search space for potential quadruplets. By using two nested loops to fix the first two numbers, we can then apply the two-pointer technique to find the remaining two numbers that complete the quadruplet.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**1. Sorting:** First, sort the array. Sorting helps to avoid duplicates and enables the use of the two-pointer technique for efficiently finding the remaining numbers.\n\n**2. Nested Loops:** Use two loops to fix the first two numbers (a and b). Then, for each pair, use two pointers (left and right) to find the remaining two numbers (c and d).\n\n**3. Two Pointers:** For the fixed pair a and b, use two pointers (left starting from b+1 and right starting from the end of the array). Adjust the pointers based on the sum of the four numbers:\n\n- If the sum equals the target, record the quadruplet and move both pointers inward.\n- If the sum is less than the target, increment the left pointer to increase the sum.\n- If the sum is greater than the target, decrement the right pointer to reduce the sum.\n\n**4. Avoiding Duplicates:** After finding a valid quadruplet, move both pointers (left and right) past any duplicate values to ensure unique results.\n\n **5. Early Exit:** Use early exit conditions to avoid unnecessary computations:\n\n- If the smallest possible sum with the current numbers is greater than the target, stop further processing.\n- If the largest possible sum with the current numbers is less than the target, skip to the next iteration.\n# Complexity\n###  Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity is O(n^3), where n is the number of elements in the array. Sorting the array takes \nO(nlogn), and for each pair of numbers, the two-pointer technique takes O(n). Since we are looping over the array for two fixed numbers and then using the two-pointer technique, the overall time complexity is O(n^3).\n### Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is O(1) if we exclude the space needed for the result storage. Sorting the array is done in-place, and we only use a constant amount of extra space for variables and pointers. However, the result storage could take O(k) space, where k is the number of quadruplets found.\n# Code\n```python3 []\nclass Solution:\n    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n        nums.sort()  # Sort the array first\n        n = len(nums)\n        result = []\n        \n        # Iterate over the first two numbers\n        for i in range(n - 3):\n            # Early exit if the smallest sum exceeds the target\n            if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:\n                break\n            \n            # Skip duplicates for the first number\n            if i > 0 and nums[i] == nums[i - 1]:\n                continue\n            \n            # Early exit if the largest possible sum is less than the target\n            if nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target:\n                continue\n            \n            for j in range(i + 1, n - 2):\n                # Skip duplicates for the second number\n                if j > i + 1 and nums[j] == nums[j - 1]:\n                    continue\n                \n                # Early exit for the second number\n                if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:\n                    break\n\n                if nums[i] + nums[j] + nums[n-1] + nums[n-2] < target:\n                    continue\n                \n                # Now use two pointers for the remaining two numbers\n                left, right = j + 1, n - 1\n                while left < right:\n                    total = nums[i] + nums[j] + nums[left] + nums[right]\n                    \n                    if total == target:\n                        result.append([nums[i], nums[j], nums[left], nums[right]])\n                        left += 1\n                        right -= 1\n                        \n                        # Skip duplicates for the third number\n                        while left < right and nums[left] == nums[left - 1]:\n                            left += 1\n                        \n                        # Skip duplicates for the fourth number\n                        while left < right and nums[right] == nums[right + 1]:\n                            right -= 1\n                            \n                    elif total < target:\n                        left += 1\n                    else:\n                        right -= 1\n                        \n        return result\n```
['Array', 'Two Pointers', 'Dynamic Programming', 'Sorting', 'Python3']