4Sum

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
129 upvotes

Problem statement

You are given an array ‘NUMS’ of length ‘N’. You are also given an integer ‘TARGET’.


Return an array of all the unique quadruplets [ ‘NUMS[ a ]’, ‘NUMS[ b ]’, ‘NUMS[ c ]’, ‘NUMS[ d ]’ ] with the following conditions:


i. 0 <= a, b, c, d < ‘N’ and a, b, c, and d are distinct.

ii. NUMS[ a ] + NUMS[ b ] + NUMS[ c ] +NUMS[ d ] = TARGET


Return the array in any order.


Note:


(NUMS[ a ], NUMS[ b ], NUMS[ c ], NUMS[ d ]), (NUMS[ a ], NUMS[ d ], NUMS[ c ], NUMS[ b ]), (NUMS[ a ], NUMS[ c ], NUMS[ b ], NUMS[ d ])... all of them are treated or considered the same quadruplets.


Two quadruplets are different if there is any integer in one quadruplet which is not in the other.


The solution will be verified by the number of valid quadruplets returned. In the output, only the number of valid quadruplets will be printed.


Example: 
Input: ‘N’ = 5,  ‘TARGET’ = 5, ‘NUMS’ = [ 1, 2, 1, 0, 1 ]

Output: 1.

There is only one unique quadruplet with sum = 5 and that is [1, 2, 1, 1].
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains two integers, ‘N’ and ‘TARGET’, denoting the length of the array ‘NUMS’ and an arbitrary integer.

The second line contains ‘N’ space-separated integers.
Output format : 
Prints the number of unique quadruplets.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1:
6 8
2 2 2 2 1 3
Sample Output 1 :
2
Explanation Of Sample Input 1:
(2+2+2+2) = (2+2+1+3) = 4.
Sample Input 2:
4 4
1 1 1 0
Sample Output 2 :
0
Constraints :
4 <= N <= 100
-10^6 <= NUMS[ i ] <= 10^6
-10^6 <= TARGET <= 10^6


Time Limit: 1 sec
Hint

Can you think of a way to generate all possible quadruplets with a sum equal to target and store the unique ones only?

Approaches (2)
Bruteforce

In this approach, We can run 4 nested loops to generate all possible quadruplets. In order to remove duplicate quadruples we can use a set. There is still one problem if the quadruples are like (a, b, c, d) and (a, d, b, c) set will not treat them as the same. To solve this problem we can sort the whole array ‘NUMS’.


 

The steps are as follows:-

function fourSum( [ int ] nums, int target):

  1. Declare a 2d array 'ANS'.
  2. Declare a set 'uniqueQuad' of type array of int to store unique quadruples.
  3. Sort the array 'NUMS'.
  4. Run a loop from 'i' = 0...'N' - 1:
    • Store the value of 'NUMS[ i ]' in variable 'A'.
    • Run a loop from 'j' = ('i' + 1)...('N' - 1):
      • Store the value of 'NUMS[ j ]' in variable 'B'.
      • Run a loop from 'k' = ('j' + 1)...('N' - 1):
        • Store the value of 'NUMS[ k ]' in variable 'C'.
        • Run a loop from 'l' = ('k' + 1)...('N' - 1):
          1. Store the value of 'NUMS[ l ]' in variable 'D'.
          2. Initialize a variable 'TOTAL' with the value of 'A' + 'B' + 'C' + 'D'.
          3. If 'TOTAL' is equal to 'TARGET' then insert the array with elements {'A', 'B', 'C', 'D'} into the set 'uniqueQuad'.
  5. Iterate over the set 'uniqueQuad' and append the arrays into the 'ANS' array.
  6. Return the  'ANS' array.
Time Complexity

O( N^4 * log( N ) ), Where ‘N’ is the length of array ‘NUMS’.

 

We are running 4 nested loops and for each quadruple, we are inserting it into the set which has a time complexity of O( log( N ) ).

Hence the time complexity is O( N^4 * log( N ) ).

Space Complexity

O( N^4 ).  Where ‘N’ is the length of array ‘NUMS’.

 

We are using a set to store all unique quadruplets. In the worst case, there can be ‘N’^4 quadruplets.

Hence space complexity is O( N^4 ).

Code Solution
(100% EXP penalty)
4Sum
Full screen
Console