DSA using Apex (Salesforce)-03/100

let’s solve : Four Number sum

Q:Write a function that takes in non-empty List of distinct Integers and an integer representing a target sum. The function should find all the quadruplets that sum up to the target sum and return a list of all these quadruplets in no particular order. If no four numbers sum up to the target sum , then return an empty list.

Sample input :

List<Integer>{-10, -3, -5, 2, 15, -7, 28, -6, 12, 8, 11, 5};

targetSum = 20;

Sample output:

((15, 8, 2, -5), (-7, 28, 2, -3), (28, 5, -3, -10), (-6, 8, 28, -10), (-6, 5, 28, -7), (12, 11, 2, -5), (8, 5, 12, -5))

I urge you to pause here and try this on your own before looking at the solution below:

Solution :

public class FourNumberSum {
    
    public static List<List<Integer>> doSum(List<Integer> inputArray,Integer targetSum){
        List<List<Integer>> quadruplets  = new List<List<Integer>>();
        Map<Integer,List<List<Integer>>> numberPairMap = new Map<Integer,List<List<Integer>>>();
        for(integer i=0;i<inputArray.size();i++){
            for(integer j=i+1;j<inputArray.size();j++){
                integer newTarget = targetSum -(inputArray[i] + inputArray[j]);
                if(numberPairMap.containsKey(newTarget)){
                    for(List<Integer> pairs : numberPairMap.get(newTarget)){
                        List<Integer> temp = new List<Integer>{inputArray[i],inputArray[j],pairs[0],pairs[1]};
                        quadruplets .add(temp);
                    }
                }
            }// end of inner loop
            
            // to prevent duplicates , loop over before and add
            for(integer j=0;j<i;j++){
                List<Integer> temp = new List<Integer>{inputArray[i],inputArray[j]};
                 integer currentSum = inputArray[i] + inputArray[j];
                if(!numberPairMap.containsKey(currentSum)){
                    numberPairMap.put(currentSum,new List<List<Integer>>());
                    numberPairMap.get(currentSum).add(temp);
                }
            }
            
        }//end of outer loop 
        system.debug('@@@ result '+quadruplets);
        return quadruplets ;
    }
}

Explaination :

The function initializes an empty list called quadruplets to store the resulting quadruplets and a map called numberPairMap to keep track of pairs of numbers and their sums.

The code uses nested loops to iterate over the elements of the input array. The outer loop iterates from the first element to the second-to-last element, and the inner loop iterates from the element next to the outer loop’s current element to the last element.

In each iteration of the inner loop, the code calculates the new target sum (newTarget) by subtracting the sum of the current pair of numbers (inputArray[i] and inputArray[j]) from the original target sum.

It then checks if the numberPairMap contains the newTarget as a key. If it does, it means that there are pairs of numbers in the input array whose sum is equal to the newTarget. In that case, the code iterates over each pair in the value associated with the newTarget key and creates a new quadruplet by combining the current pair with the pairs from numberPairMap. The quadruplet is added to the quadruplets list.

After the inner loop completes, the code enters another loop that iterates over the elements of the input array before the current outer loop index. This is done to prevent duplicates. In each iteration, the code creates a pair of numbers (inputArray[i] and inputArray[j]) and calculates their sum (currentSum).

The code checks if the numberPairMap already contains the currentSum as a key. If it doesn’t, a new entry is added to the map with currentSum as the key and an empty list as the value. Then, the current pair is added to the list associated with the currentSum key in the numberPairMap.

Finally, the function returns the quadruplets list.

I hope you found this helpful. If you have a better way to solve it, do let me know in the comments .

Thanks!