Last Updated: 22 Jul, 2022

4Sum

Moderate

Solve now

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

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.

Solve now

Approaches

01 Approach

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):

Declare a 2d array 'ANS'.
Declare a set 'uniqueQuad' of type array of int to store unique quadruples.
Sort the array 'NUMS'.
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'.
Iterate over the set 'uniqueQuad' and append the arrays into the 'ANS' array.
Return the 'ANS' array.

Solve now

02 Approach

In this approach, the idea is to use two pointers to optimize the previous approach. We will first sort the array. We can iterate over the array ‘NUMS’ ( ‘i’ = 0…’N’-1) for variable ‘A’ then we can make a nested loop( ‘j’ = ‘i’ +1 to ‘N’ - 1) to iterate over ‘NUMS’ for variable ‘B’ and for variable ‘C’ and ‘D’ we will run only one loop. We will two pointers ‘LEFT’ and ‘RIGHT’ where ‘LEFT’ points to ‘NUMS[ j + 1]’ and ‘RIGHT’ points to the last element. Let us consider value of ‘NUMS[ left ] = ‘C’ and ‘NUMS[ right ] =’D’. Total = ‘A’ + ‘B’ + ‘C’ + ‘D’. If the total is equal to the target then we push it into the array and increment ‘LEFT’ by 1 and decrement ‘RIGHT’ by 1. Else if the total is greater than the target then we decrement ‘RIGHT’ by 1 else we increment ‘LEFT’ by 1.

To remove the duplicates, for each loop when we are incrementing the index we will keep on incrementing it till the value is the same. For example if ‘NUMS[ i ] = 4 then increment ‘i’ until ‘NUMS[ i ]’ != 4.

The steps are as follows:-

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

Declare a 2d array 'ANS'.
Sort the array 'NUMS'.
Run a loop from 'i' = 0...'N' - 1:
- Store the value of 'NUMS[ i ]' into the variable 'A'.
- Run a loop from 'j' = ('i' + 1)...('N' - 1):
  - Store the value of 'NUMS[ j ]' into the variable 'B'.
  - Initialize two variables 'LEFT' and 'RIGHT' with values ('j' + 1) and ('N' - 1) respectively.
  - Run a loop while 'LEFT' < 'RIGHT':
    - Store the value of 'NUMS[ left ]' into the variable 'C'.
    - Store the value of 'NUMS[ right ]' into the variable 'D'.
    - Initialize a variable 'TOTAL' with the value of 'A' + 'B' + 'C' + 'D'.
    - If 'TOTAL' is equal to the target then:
      1. Append the array {'A', 'B', 'C', 'D'} into the 'ANS' array.
      2. Increment the 'LEFT' variable by 1.
      3. Run a loop while 'LEFT' < 'RIGHT' and 'NUMS[ left ]' is equal to 'NUMS[ left - 1 ]':
        Increment 'LEFT' by 1.
      4. Decrement the' RIGHT' variable by 1.
      5. Run a loop while 'LEFT' < 'RIGHT' and 'NUMS[ right ]' is equal to 'NUMS[ right + 1 ]':
        Decrement 'RIGHT' by 1.
    - Else if 'TOTAL' > 'TARGET' decrement 'RIGHT' by 1.
    - Else increment 'LEFT' by 1.
  - Run a loop while 'j' < 'N' and 'NUMS[ j ]' is equal to 'B':
    - Increment 'j' by 1.
- Run a loop while 'i' < 'N' and 'NUMS[ i ]' is equal to 'A':
  - Increment 'i' by 1.
Return the value of variable 'ANS'.

Solve now