4Sum Leetcode Solution
In this tutorial, we will solve the 4sum leetcode problem in python.
Task:
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < na,b,c, anddare distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
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 = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
Constraints:
1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
Solution:
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
if not nums or len(nums) < 4:
return []
s, m = set(), len(nums)
nums.sort()
for i in range(m-3):
for j in range(i+1,m-2):
l, r = j+1, m-1
while l < r:
if (nums[i]+nums[j]+nums[l]+nums[r]) == target:
s.add((nums[i], nums[j], nums[l], nums[r]))
l+=1
r-=1
elif (nums[i]+nums[j]+nums[l]+nums[r]) < target:
l+=1
elif (nums[i]+nums[j]+nums[l]+nums[r]) > target:
r-=1
return list(s)
Steps
step1: First we make the base case for the problem which is if nums is empty or its length is less than 4.
step2: then we declare an empty set and m variable to store the length of the nums and then sort the nums.
step3: then we loop till the m-3 and added another inner loop which will run from index+1 till m-2.
step4: inside the inner loop we declare and initialize our left and right pointers for the approach.
step5: inside the inner loop we also added a while loop with the condition as left < right and added a couple of if-else statements to check the condition and added it to the set s while updating the pointers.
step6: after the outer loop we return the set s with type casting as a list.
