Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Notice that the solution set must not contain duplicate quadruplets.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [], target = 0 Output: []
Constraints:
0 <= nums.length <= 200-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9
The description was taken from https://leetcode.com/problems/4sum/.
#O(N^3) Time, O(1) Space, Excluding Output Space
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
if not nums or len(nums) < 4:
return []
result = []
nums.sort()
for anchor in range(len(nums)-3):
if anchor > 0 and nums[anchor] == nums[anchor-1]:
continue
for left in range(anchor + 1, len(nums) - 2):
if left > anchor + 1 and nums[left] == nums[left-1]:
continue
mid = left + 1
right = len(nums) - 1
while mid < right:
four = [nums[anchor], nums[left], nums[mid], nums[right]]
four_sum = sum(four)
if four_sum == target:
result.append(four)
mid += 1
right -= 1
while mid < right and nums[mid] == nums[mid-1]:
mid += 1
while mid < right and nums[right] == nums[right+1]:
right -= 1
elif four_sum < target:
mid += 1
else:
right -= 1
return resultThis problem is just an extension of Three-Sum.
What we had to do in the previous problem was sort the array and then iterate through it with a left pointer which was an anchor for us with two more pointers. The other two, the mid and right pointers were used to try and find a pair of numbers to sum with the left pointer that would allow the sum of all three to be equal to the target. If the three-sum was too high, we moved the right pointer to a lesser number. If it is too low, we moved the mid-pointer to a greater number.
The only thing we need to add to the previous algorithm to solve this one is the addition of an extra anchor, that's it.
First off, if we don't have at least four numbers then we have no four-sum, we'll return false if that's true.
if not nums or len(nums) < 4:
return []
Otherwise, let's start by initializing our result array and sorting our input.
result = []
nums.sort()
Next, we will begin traversing the array with our left anchor, we could also picture this as our far-left pointer. We only want to go up until three indices before the end of the array so that we have room to fit in a left, mid, and right pointer.
for anchor in range(len(nums)-3):
Once our anchor pointer has gone past the first index and has a previous element, we will check if that element is the same as the current one. If it is, we will skip it so that we don't visit the same number twice.
if anchor > 0 and nums[anchor] == nums[anchor-1]:
continue
Next, we will set the range that we'll search to find three numbers to sum with the anchor as one past the anchor and two before the end of the array.
This way, we can fit a middle and a right pointer in.
for left in range(anchor + 1, len(nums) - 2):
Same as earlier, if the left pointer has a previous index and has a duplicate element as the previous, we will skip this iteration.
if left > anchor + 1 and nums[left] == nums[left-1]:
continue
Next, we will set our middle and right pointers to one index from the left and the last index of the array respectively.
mid = left + 1
right = len(nums) - 1
Now, we will begin trying to find a pair of numbers using the mid and right pointers that will sum to the left and anchor numbers to result in the target value.
While the pointers haven't overlapped, we still have numbers to consider.
while mid < right:
Let's group these four numbers in an array and calculate the sum.
four = [nums[anchor], nums[left], nums[mid], nums[right]]
four_sum = sum(four)
If the four-sum is equal to the target, we will append these four numbers to the result and move both pointers inward to continue searching for more numbers that sum with the left pointer and anchor to equal the target.
if four_sum == target:
result.append(four)
mid += 1
right -= 1
If we found a valid four-sum, we'll want to handle the scenario where we'd get these four numbers again.
If the pointers haven't overlapped and either pointer has the same number that we just moved it from, we will skip the current number it is at because we already accounted for it.
Since we moved the numbers before checking the previous number, we can ensure we won't get an index out of bounds.
while mid < right and nums[mid] == nums[mid-1]:
mid += 1
while mid < right and nums[right] == nums[right+1]:
right -= 1
If the four-sum is less than the target, we will move the mid-pointer to a greater number.
elif four_sum < target:
mid += 1
If the four-sum is greater than the target, we will move the right pointer to a lesser number.
else:
right -= 1
Once we have finished collecting each four-sum, we will return the result.
return result