4Sum Ii

                                            
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> mapAB;
        int count = 0;
        
        for (int a : nums1) {
            for (int b : nums2) {
                mapAB[a + b]++;
            }
        }
        
        for (int c : nums3) {
            for (int d : nums4) {
                if (mapAB.find(-c - d) != mapAB.end()) {
                    count += mapAB[-c - d];
                }
            }
        }
        
        return count;
    }
};

                                            
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                int sum = num1 + num2;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        
        for (int num3 : nums3) {
            for (int num4 : nums4) {
                int target = - (num3 + num4);
                count += map.getOrDefault(target, 0);
            }
        }
        
        return count;
    }
}

                                            
class Solution(object):
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        count = 0
        sum_map = {}
        
        for i in nums1:
            for j in nums2:
                if i + j in sum_map:
                    sum_map[i + j] += 1
                else:
                    sum_map[i + j] = 1
        
        for k in nums3:
            for l in nums4:
                if -k - l in sum_map:
                    count += sum_map[-k - l]
        
        return count

                                            
int cmp(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int fourSumCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* nums3, int nums3Size, int* nums4, int nums4Size) {
    int count = 0;
    int *sumsAB = (int*)malloc(nums1Size * nums2Size * sizeof(int));
    int *sumsCD = (int*)malloc(nums3Size * nums4Size * sizeof(int));
    
    for(int i = 0; i < nums1Size; i++) {
        for(int j = 0; j < nums2Size; j++) {
            sumsAB[i*nums2Size + j] = nums1[i] + nums2[j];
        }
    }
    
    for(int i = 0; i < nums3Size; i++) {
        for(int j = 0; j < nums4Size; j++) {
            sumsCD[i*nums4Size + j] = nums3[i] + nums4[j];
        }
    }
    
    qsort(sumsAB, nums1Size * nums2Size, sizeof(int), cmp);
    qsort(sumsCD, nums3Size * nums4Size, sizeof(int), cmp);
    
    int i = 0, j = nums3Size * nums4Size - 1;
    while(i < nums1Size * nums2Size && j >= 0) {
        if(sumsAB[i] + sumsCD[j] == 0) {
            int cnt1 = 1, cnt2 = 1;
            i++; j--;
            while(i < nums1Size * nums2Size && sumsAB[i] == sumsAB[i - 1]) {
                i++;
                cnt1++;
            }
            while(j >= 0 && sumsCD[j] == sumsCD[j + 1]) {
                j--;
                cnt2++;
            }
            count += cnt1 * cnt2;
        } else if(sumsAB[i] + sumsCD[j] < 0) {
            i++;
        } else {
            j--;
        }
    }
    
    free(sumsAB);
    free(sumsCD);
    
    return count;
}

                                            
public class Solution {
    public int FourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Dictionary<int, int> map = new Dictionary<int, int>();
        int count = 0;
        
        foreach (var num1 in nums1) {
            foreach (var num2 in nums2) {
                int sum1 = num1 + num2;
                if (!map.ContainsKey(sum1)) {
                    map[sum1] = 0;
                }
                map[sum1]++;
            }
        }
        
        foreach (var num3 in nums3) {
            foreach (var num4 in nums4) {
                int sum2 = -(num3 + num4);
                if (map.ContainsKey(sum2)) {
                    count += map[sum2];
                }
            }
        }
        
        return count;
    }
}

                                            
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @param {number[]} nums4
 * @return {number}
 */
const fourSumCount = (nums1, nums2, nums3, nums4) => {
    const map = new Map();
    let count = 0;

    for (const num1 of nums1) {
        for (const num2 of nums2) {
            const sum = num1 + num2;
            map.set(sum, (map.get(sum) || 0) + 1);
        }
    }

    for (const num3 of nums3) {
        for (const num4 of nums4) {
            const target = -1 * (num3 + num4);
            if (map.has(target)) {
                count += map.get(target);
            }
        }
    }

    return count;
};

                                            
function fourSumCount(nums1: number[], nums2: number[], nums3: number[], nums4: number[]): number {
    const map: Map<number, number> = new Map();
    
    let count = 0;
    
    for (let num1 of nums1) {
        for (let num2 of nums2) {
            const sum1_2 = num1 + num2;
            if (map.has(sum1_2)) {
                map.set(sum1_2, map.get(sum1_2)! + 1);
            } else {
                map.set(sum1_2, 1);
            }
        }
    }
    
    for (let num3 of nums3) {
        for (let num4 of nums4) {
            const sum3_4 = num3 + num4;
            if (map.has(-sum3_4)) {
                count += map.get(-sum3_4)!;
            }
        }
    }
    
    return count;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @param Integer[] $nums3
     * @param Integer[] $nums4
     * @return Integer
     */
    function fourSumCount($nums1, $nums2, $nums3, $nums4) {
        $map = [];
        $count = 0;
        foreach ($nums1 as $num1) {
            foreach ($nums2 as $num2) {
                $sum = $num1 + $num2;
                if (array_key_exists($sum, $map)) {
                    $map[$sum]++;
                } else {
                    $map[$sum] = 1;
                }
            }
        }
        
        foreach ($nums3 as $num3) {
            foreach ($nums4 as $num4) {
                $target = -$num3 - $num4;
                if (array_key_exists($target, $map)) {
                    $count += $map[$target];
                }
            }
        }
        
        return $count;
    }
}

                                            
class Solution {
    func fourSumCount(_ nums1: [Int], _ nums2: [Int], _ nums3: [Int], _ nums4: [Int]) -> Int {
        var count = 0
        var sum1and2 = [Int: Int]()
        
        for num1 in nums1 {
            for num2 in nums2 {
                let sum = num1 + num2
                sum1and2[sum, default: 0] += 1
            }
        }
        
        for num3 in nums3 {
            for num4 in nums4 {
                let target = -(num3 + num4)
                if let val = sum1and2[target] {
                    count += val
                }
            }
        }
        
        return count
    }
}

                                            
class Solution {
    fun fourSumCount(nums1: IntArray, nums2: IntArray, nums3: IntArray, nums4: IntArray): Int {
        val map = mutableMapOf<Int, Int>()
        var count = 0
        
        for (num1 in nums1) {
            for (num2 in nums2) {
                val sum = num1 + num2
                map[sum] = map.getOrDefault(sum, 0) + 1
            }
        }
        
        for (num3 in nums3) {
            for (num4 in nums4) {
                val complement = -(num3 + num4)
                count += map.getOrDefault(complement, 0)
            }
        }
        
        return count
    }
}

                                            
class Solution {
  int fourSumCount(List<int> nums1, List<int> nums2, List<int> nums3, List<int> nums4) {
    Map<int, int> map = {};
    int count = 0;

    for (int num1 in nums1) {
      for (int num2 in nums2) {
        int sum = num1 + num2;
        map[sum] = (map[sum] ?? 0) + 1;
      }
    }

    for (int num3 in nums3) {
      for (int num4 in nums4) {
        int complement = -(num3 + num4);
        if (map.containsKey(complement)) {
          count += map[complement]!;
        }
      }
    }

    return count;
  }
}

                                            
func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    count := 0
    sumMap := make(map[int]int)

    for _, n1 := range nums1 {
        for _, n2 := range nums2 {
            sumMap[n1+n2]++
        }
    }

    for _, n3 := range nums3 {
        for _, n4 := range nums4 {
            count += sumMap[-(n3 + n4)]
        }
    }

    return count
}

                                            
# @param {Integer[]} nums1
# @param {Integer[]} nums2
# @param {Integer[]} nums3
# @param {Integer[]} nums4
# @return {Integer}
def four_sum_count(nums1, nums2, nums3, nums4)
    sum_map = {}
    count = 0
    
    nums1.each do |a|
        nums2.each do |b|
            sum_map[a + b] = sum_map.fetch(a + b, 0) + 1
        end
    end
    
    nums3.each do |c|
        nums4.each do |d|
            count += sum_map.fetch(-(c + d), 0)
        end
    end
    
    count
end

                                            
object Solution {
    def fourSumCount(nums1: Array[Int], nums2: Array[Int], nums3: Array[Int], nums4: Array[Int]): Int = {
        var count = 0
        val map = scala.collection.mutable.Map.empty[Int, Int]

        for {
            a <- nums1
            b <- nums2
        } {
            val sum = a + b
            map(sum) = map.getOrElse(sum, 0) + 1
        }

        for {
            c <- nums3
            d <- nums4
        } {
            val target = -(c + d)
            if (map.contains(target)) {
                count += map(target)
            }
        }

        count
    }
}

                                            
impl Solution {
    pub fn four_sum_count(nums1: Vec<i32>, nums2: Vec<i32>, nums3: Vec<i32>, nums4: Vec<i32>) -> i32 {
        use std::collections::HashMap;

        let mut count = 0;
        let mut map = HashMap::new();

        for &a in &nums1 {
            for &b in &nums2 {
                *map.entry(a + b).or_insert(0) += 1;
            }
        }

        for &c in &nums3 {
            for &d in &nums4 {
                if let Some(&val) = map.get(&-(c + d)) {
                    count += val;
                }
            }
        }

        count
    }
}

                                            
(define/contract (four-sum-count nums1 nums2 nums3 nums4)
  (-> (listof exact-integer?) (listof exact-integer?) (listof exact-integer?) (listof exact-integer?) exact-integer?)
  
  (define hash-table (make-hash))
  (define (addToHashTable ht val)
    (hash-set! ht val (add1 (hash-ref ht val 0))))
  
  (define (countPairsSumToZero ht lst1 lst2)
    (for* ([num1 lst1] [num2 lst2])
      (addToHashTable ht (+ num1 num2))))
  
  (countPairsSumToZero hash-table nums1 nums2)
  
  (define (countTotalPairsSumToZero ht lst1 lst2)
    (define count 0)
    (for* ([num1 lst1] [num2 lst2])
      (define complement (- 0 (+ num1 num2)))
      (set! count (+ count (hash-ref ht complement 0))))
    count)
  
  (define total-count 0)
  (set! total-count (+ total-count (countTotalPairsSumToZero hash-table nums3 nums4)))
  
  total-count)

                                            
defmodule Solution do
  @spec four_sum_count(nums1 :: [integer], nums2 :: [integer], nums3 :: [integer], nums4 :: [integer]) :: integer

  def four_sum_count(nums1, nums2, nums3, nums4) do
    count = Enum.reduce(nums1, 0, fn a, acc1 ->
      Enum.reduce(nums2, acc1, fn b, acc2 ->
        Enum.reduce(nums3, acc2, fn c, acc3 ->
          Enum.reduce(nums4, acc3, fn d, acc4 ->
            acc4 + if a + b + c + d == 0, do: 1, else: 0
          end)
        end)
      end)
    end)
  end
end

To solve this coding challenge, you need to find the number of tuples (i, j, k, l) for four integer arrays such that the sum of the elements from each array is zero. The optimal approach leverages the use of a hash map to efficiently count and check the required sums. Here's a step-by-step explanation and methodology to solve this challenge:

# Explanation

Understand the Problem:

We are given four arrays: nums1, nums2, nums3, and nums4.
We need to find the count of tuples (i, j, k, l) where indices i, j, k, l come from arrays nums1, nums2, nums3, and nums4 respectively, and the sum of the elements at these indices is zero.

Optimal Approach:

Use a hash map to store and count the sums of pairs of elements.
First, calculate the sums of all pairs from nums1 and nums2, and store the sum in a hash map.
The key in this hash map will be the sum, and the value will be the count of how many times this sum appears.
Then, for each pair from nums3 and nums4, check if the negative of their sum exists in the hash map. If it does, it means that those pairs from nums1 and nums2 complement the pairs from nums3 and nums4 to sum to zero.
Count how many times these complementary sums appear.

Detailed Steps in Pseudocode

Initialize a Count and a Hash Map:

Set
count

to zero. This will store the final count of tuples.
Initialize an empty hash map
sum_map

.

Populate the Hash Map with Pairs from nums1 and nums2:

Iterate over each element
i

in
nums1

.
For each element
i

, iterate over each element
j

in
nums2

.
Calculate the sum of
i

and
j

.
If this sum already exists in
sum_map

, increment its count.
If it does not exist, add it to
sum_map

with an initial count of 1.

Check for Complementary Pairs from nums3 and nums4:

Iterate over each element
k

in
nums3

.
For each element
k

, iterate over each element
l

in
nums4

.
Calculate the sum of
k

and
l

.
Check if the negative of this sum exists in
sum_map

.
If it exists, increase the count by the value from the hash map, as this value represents how many pairs from nums1 and nums2 can complement the current pair from nums3 and nums4 to sum to zero.

Return the Count:

Finally, return the total
count

of such tuples.

# Pseudocode

                                            
# Initialize count to store the final number of valid tuples
count = 0 

# Initialize an empty hash map to store sums of pairs from nums1 and nums2
sum_map = {}

# Compute all sums of pairs from nums1 and nums2
for each element in nums1:
    for each element in nums2:
        pair_sum = element from nums1 + element from nums2
        if pair_sum in sum_map:
            sum_map[pair_sum] = sum_map[pair_sum] + 1  # Increase count of this sum
        else:
            sum_map[pair_sum] = 1  # Initialize this sum in the map

# Check all pairs from nums3 and nums4
for each element in nums3:
    for each element in nums4:
        pair_sum = element from nums3 + element from nums4
        complement_sum = -pair_sum
        if complement_sum in sum_map:
            count = count + sum_map[complement_sum]  # Increment the count by the number of ways to get this complementary sum

# Return the total count of tuples
return count

The above pseudocode provides a detailed plan to solve the problem by efficiently computing the count of tuples that sum up to zero. The use of the hash map ensures that the solution is optimized for performance, avoiding the need for a brute-force approach which would be computationally expensive given the constraints.