4sum Problem Leetcode – Python Solutions

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

4sum problem leetcode
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, and d 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:

To get the solution visit https://hecodesit.com/4sum-problem-leetcode-python-solutions/