LeetCode has a Medium coding Problem in Its’ Algorithm Section “4sum problem Leetcode”. Today We are going to solve this problem. LeetCode Link of the Problem is HERE
Question
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 < n
a
,b
,c
, andd
are distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Examples to 4sum problem leetcode
Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
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
4sum problem leetcode Solution
The Skeleton Code given in Leetcode is
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
Firstly, Sort the given array of integers. Create a variable result that will store the list containing values of output. Create another variable lookup, which will have keys as the addition of two numbers and values as a list having a position of two numbers when added and give the key.
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums, result, lookup = sorted(nums), [], collections.defaultdict(list)
Secondly, Run two loops one starting from the start of the integers array and one starting from the second element. Fill up the values in the lookup dictionary.
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums, result, lookup = sorted(nums), [], collections.defaultdict(list)
for i in xrange(0, len(nums) - 1):
for j in xrange(i + 1, len(nums)):
is_duplicated = False
for [x, y] in lookup[nums[i] + nums[j]]:
if nums[x] == nums[i]:
is_duplicated = True
break
if not is_duplicated:
lookup[nums[i] + nums[j]].append([i, j])
Check for the other two values which will be added with the values in the lookup dictionary and must return the target value. Don’t forget about the constraints that, a < b < c < d.
Complete Solution:
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums, result, lookup = sorted(nums), [], collections.defaultdict(list)
# print(lookup)
for i in xrange(0, len(nums) - 1):
for j in xrange(i + 1, len(nums)):
is_duplicated = False
for [x, y] in lookup[nums[i] + nums[j]]:
if nums[x] == nums[i]:
is_duplicated = True
break
if not is_duplicated:
lookup[nums[i] + nums[j]].append([i, j])
print(lookup)
ans = {}
for c in xrange(2, len(nums)):
for d in xrange(c+1, len(nums)):
if target - nums[c] - nums[d] in lookup:
for [a, b] in lookup[target - nums[c] - nums[d]]:
if b < c:
quad = [nums[a], nums[b], nums[c], nums[d]]
quad_hash = " ".join(str(quad))
if quad_hash not in ans:
ans[quad_hash] = True
result.append(quad)
return result
READ MORE
Python-related posts Visit HERE
C++ related posts Visit HERE
Databases related posts Visit HERE
Data Structures related posts visit HERE
Algorithms related posts visit HERE
Data Science related posts visit HERE