4Sum LeetCode Solution

Last updated on October 5th, 2024 at 09:10 pm

Here, We see 4Sum LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Dynamic Programming, Recursion

Companies

LinkedIn

Level of Question

Medium

4Sum LeetCode Solution

4Sum LeetCode Solution

Problem Statement

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.

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]]

1. 4Sum Leetcode Solution C++

class Solution {
public:
    vector&lt;vector&lt;int&gt;&gt; fourSum(vector&lt;int&gt;&amp; nums, int target) {
        vector&lt;vector&lt;int&gt;&gt; total;
        int n = nums.size();
        if(n&lt;4)  return total;
        sort(nums.begin(),nums.end());
        for(int i=0;i&lt;n-3;i++)
        {
            if(i&gt;0&amp;&amp;nums[i]==nums[i-1]) continue;
            if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]&gt;target) break;
            if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]&lt;target) continue;
            for(int j=i+1;j&lt;n-2;j++)
            {
                if(j&gt;i+1&amp;&amp;nums[j]==nums[j-1]) continue;
                if(nums[i]+nums[j]+nums[j+1]+nums[j+2]&gt;target) break;
                if(nums[i]+nums[j]+nums[n-2]+nums[n-1]&lt;target) continue;
                int left=j+1,right=n-1;
                while(left&lt;right){
                    int sum=nums[left]+nums[right]+nums[i]+nums[j];
                    if(sum&lt;target) left++;
                    else if(sum&gt;target) right--;
                    else{
                        total.push_back(vector&lt;int&gt;{nums[i],nums[j],nums[left],nums[right]});
                        do{left++;}while(nums[left]==nums[left-1]&amp;&amp;left&lt;right);
                        do{right--;}while(nums[right]==nums[right+1]&amp;&amp;left&lt;right);
                    }
                }
            }
        }
        return total;
    }
};

2. 4Sum Leetcode Solution Java

class Solution {
public List&lt;List&lt;Integer&gt;&gt; fourSum(int[] nums, int target) {
		ArrayList&lt;List&lt;Integer&gt;&gt; res = new ArrayList&lt;List&lt;Integer&gt;&gt;();
		int len = nums.length;
		if (nums == null || len &lt; 4)
			return res;
		Arrays.sort(nums);
		int max = nums[len - 1];
		if (4 * nums[0] &gt; target || 4 * max &lt; target)
			return res;
		int i, z;
		for (i = 0; i &lt; len; i++) {
			z = nums[i];
			if (i &gt; 0 &amp;&amp; z == nums[i - 1])
				continue;
			if (z + 3 * max &lt; target)
				continue;
			if (4 * z &gt; target)
				break;
			if (4 * z == target) {
				if (i + 3 &lt; len &amp;&amp; nums[i + 3] == z)
					res.add(Arrays.asList(z, z, z, z));
				break;
			}
			threeSumForFourSum(nums, target - z, i + 1, len - 1, res, z);
		}
		return res;
	}
	public void threeSumForFourSum(int[] nums, int target, int low, int high, ArrayList&lt;List&lt;Integer&gt;&gt; fourSumList,
			int z1) {
		if (low + 1 &gt;= high)
			return;
		int max = nums[high];
		if (3 * nums[low] &gt; target || 3 * max &lt; target)
			return;
		int i, z;
		for (i = low; i &lt; high - 1; i++) {
			z = nums[i];
			if (i &gt; low &amp;&amp; z == nums[i - 1])
				continue;
			if (z + 2 * max &lt; target)
				continue;
			if (3 * z &gt; target)
				break;
			if (3 * z == target) {
				if (i + 1 &lt; high &amp;&amp; nums[i + 2] == z)
					fourSumList.add(Arrays.asList(z1, z, z, z));
				break;
			}
			twoSumForFourSum(nums, target - z, i + 1, high, fourSumList, z1, z);
		}
	}
	public void twoSumForFourSum(int[] nums, int target, int low, int high, ArrayList&lt;List&lt;Integer&gt;&gt; fourSumList,
			int z1, int z2) {
		if (low &gt;= high)
			return;
		if (2 * nums[low] &gt; target || 2 * nums[high] &lt; target)
			return;
		int i = low, j = high, sum, x;
		while (i &lt; j) {
			sum = nums[i] + nums[j];
			if (sum == target) {
				fourSumList.add(Arrays.asList(z1, z2, nums[i], nums[j]));
				x = nums[i];
				while (++i &lt; j &amp;&amp; x == nums[i])
					;
				x = nums[j];
				while (i &lt; --j &amp;&amp; x == nums[j])
					;
			}
			if (sum &lt; target)
				i++;
			if (sum &gt; target)
				j--;
		}
		return;
	}
}

3. 4Sum Leetcode Solution JavaScript

var fourSum = function(nums, target) {
    nums.sort((a, b) =&gt; a - b);
    const result = []
    for(let i = 0; i &lt; nums.length - 3; i++) {
        for(let j = i + 1; j &lt; nums.length - 2; j++) {
            let low = j + 1;
            let high = nums.length - 1

            while(low &lt; high) {
                const sum = nums[i] + nums[j] + nums[low] + nums[high];
                if(sum === target) {
                    result.push([nums[i], nums[j], nums[low], nums[high]])
                    while(nums[low] === nums[low + 1]) low++;
                    while(nums[high] === nums[high - 1]) high--;
                    low++;
                    high--;
                } else if(sum &lt; target) {
                    low++
                } else {
                    high--
                }
            }   
            while(nums[j] === nums[j + 1]) j++;
        }   
        while(nums[i] === nums[i + 1]) i++;
    }
    return result
};

4. 4Sum Leetcode Solution Python

class Solution(object):
    def fourSum(self, nums, target):
        nums.sort()
        results = []
        self.findNsum(nums, target, 4, [], results)
        return results
    def findNsum(self, nums, target, N, result, results):
        if len(nums) &lt; N or N &lt; 2: return
        if N == 2:
            l,r = 0,len(nums)-1
            while l &lt; r:
                if nums[l] + nums[r] == target:
                    results.append(result + [nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while l &lt; r and nums[l] == nums[l - 1]:
                        l += 1
                    while r &gt; l and nums[r] == nums[r + 1]:
                        r -= 1
                elif nums[l] + nums[r] &lt; target:
                    l += 1
                else:
                    r -= 1
        else:
            for i in range(0, len(nums)-N+1):
                if target &lt; nums[i]*N or target &gt; nums[-1]*N:
                    break
                if i == 0 or i &gt; 0 and nums[i-1] != nums[i]:
                    self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
        return
Scroll to Top