Wherever a hash is needed, you will find the presence of a map.

# Problem 454. 4Sum II

LeetCode problem link (opens new window)

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] = 0.

To make the problem a bit easier, all A, B, C, D have the same length, N, where 0 ≤ N ≤ 500. All integers are in the range of -2^28 to 2^28 - 1, and the result is guaranteed to be at most 2^31 - 1.

Example:

Input:

A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:

Explanation:

Two tuples such as:

(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

# Thoughts

At first glance, this problem appears similar to 0015. 3Sum (opens new window) and 0018. 4Sum (opens new window), but it is quite different.

This problem is a classic example of using hashing, whereas 0015. 3Sum (opens new window) and 0018. 4Sum (opens new window) are not suitable for a hashing approach, because using hashing in the 3Sum and 4Sum problems to achieve de-duplication without a timeout is very challenging, with many details needing handling.

This problem involves four independent arrays; we just need to find A[i] + B[j] + C[k] + D[l] = 0 without considering duplicate quadruples that sum to zero, making it much simpler compared to Problem 18, 4Sum, and Problem 15, 3Sum!

If this problem were to be of increased difficulty: imagine being given a single array (instead of four) and asked to find four elements that sum to zero, with the result not containing duplicate quadruples — you might want to think about this scenario. Future articles will cover it.

Steps to solve this problem:

Firstly, define an unordered_map where the key holds the sum of two numbers from arrays A and B, and the value holds the count of occurrences of these sums.
Traverse arrays A and B, and count the sums of their elements while storing these counts in the map.
Define an integer variable count, which will hold the count of instances where a+b+c+d = 0.
Traverse arrays C and D, and determine if 0-(c+d) exists in the map. If it does, use count to store the value from the map corresponding to this key.
Finally, return the count.

C++ Code:

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> umap; // Key: sum of a+b, Value: occurrence count of a+b
        // Traverse arrays A and B, count the sums of their elements, and store them in the map
        for (int a : A) {
            for (int b : B) {
                umap[a + b]++;
            }
        }
        int count = 0; // Count instances where a+b+c+d = 0
        // Traverse arrays C and D, and if 0-(c+d) exists in the map, accumulate its occurrence count
        for (int c : C) {
            for (int d : D) {
                if (umap.find(0 - (c + d)) != umap.end()) {
                    count += umap[0 - (c + d)];
                }
            }
        }
        return count;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Time Complexity: O(n^2)
Space Complexity: O(n^2), in the worst case where all sums from A and B are unique, leading to n^2 unique sums.

# Other Language Versions

# Java:

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        // Count the sums of elements from the first two arrays and store in map
        for (int i : nums1) {
            for (int j : nums2) {
                int sum = i + j;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        // Use the remaining arrays to find sums adding up to zero, and record their count
        for (int i : nums3) {
            for (int j : nums4) {
                res += map.getOrDefault(0 - i - j, 0);
            }
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Python:

(Version 1) Using Dictionary

class Solution(object):
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        # Use a dictionary to store sums of nums1 and nums2
        hashmap = dict()
        for n1 in nums1:
            for n2 in nums2:
                if n1 + n2 in hashmap:
                    hashmap[n1+n2] += 1
                else:
                    hashmap[n1+n2] = 1
        
        # If - (n1+n2) exists in nums3 and nums4, add to result
        count = 0
        for n3 in nums3:
            for n4 in nums4:
                key = - n3 - n4
                if key in hashmap:
                    count += hashmap[key]
        return count

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

(Version 2) Using Dictionary

class Solution(object):
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        # Use a dictionary to store sums of nums1 and nums2
        hashmap = dict()
        for n1 in nums1:
            for n2 in nums2:
                hashmap[n1+n2] = hashmap.get(n1+n2, 0) + 1
        
        # If - (n1+n2) exists in nums3 and nums4, add to result
        count = 0
        for n3 in nums3:
            for n4 in nums4:
                key = - n3 - n4
                if key in hashmap:
                    count += hashmap[key]
        return count

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(Version 3) Using defaultdict

from collections import defaultdict 
class Solution:
    def fourSumCount(self, nums1: list, nums2: list, nums3: list, nums4: list) -> int:
        rec, cnt = defaultdict(lambda : 0), 0
        for i in nums1:
            for j in nums2:
                rec[i+j] += 1
        for i in nums3:
            for j in nums4:
                cnt += rec.get(-(i+j), 0) 
        return cnt

1
2
3
4
5
6
7
8
9
10
11

# Go:

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {  
    m := make(map[int]int)  
    count := 0  
  
    // Construct map with sums of nums1 and nums2  
    for _, v1 := range nums1 {  
        for _, v2 := range nums2 {  
            m[v1+v2]++  
        }  
    }  
  
    // Traverse nums3 and nums4, check if -c-d exists in map  
    for _, v3 := range nums3 {  
        for _, v4 := range nums4 {  
            sum := -v3 - v4  
            if countVal, ok := m[sum]; ok {  
                count += countVal  
            }  
        }  
    }  
  
    return count  
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# JavaScript:

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @param {number[]} nums4
 * @return {number}
 */
var fourSumCount = function(nums1, nums2, nums3, nums4) {
    const twoSumMap = new Map();
    let count = 0;
    // Count the sums of nums1 and nums2 elements and store them in the map
    for(const n1 of nums1) {
        for(const n2 of nums2) {
            const sum = n1 + n2;
            twoSumMap.set(sum, (twoSumMap.get(sum) || 0) + 1)
        }
    }
    // Find if 0-(c+d) exists in the map, then accumulate it
    for(const n3 of nums3) {
        for(const n4 of nums4) {
            const sum = n3 + n4;
            count += (twoSumMap.get(0 - sum) || 0)
        }
    }

    return count;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# TypeScript:

function fourSumCount(nums1: number[], nums2: number[], nums3: number[], nums4: number[]): number {
    let helperMap: Map<number, number> = new Map();
    let resNum: number = 0;
    let tempVal: number | undefined;
    for (let i of nums1) {
        for (let j of nums2) {
            tempVal = helperMap.get(i + j);
            helperMap.set(i + j, tempVal ? tempVal + 1 : 1);
        }
    }
    for (let k of nums3) {
        for (let l of nums4) {
            tempVal = helperMap.get(0 - (k + l));
            if (tempVal) {
                resNum += tempVal;
            }
        }
    }
    return resNum;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# PHP:

class Solution {
    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @param Integer[] $nums3
     * @param Integer[] $nums4
     * @return Integer
     */
    function fourSumCount($nums1, $nums2, $nums3, $nums4) {
        $map = [];
        foreach ($nums1 as $n1) {
            foreach ($nums2 as $n2) {
                $temp = $n1 + $n2;
                $map[$temp] = isset($map[$temp]) ? $map[$temp]+1 : 1;
            }
        }
        $count = 0;
        foreach ($nums3 as $n3) {
            foreach ($nums4 as $n4) {
                $temp = 0 - $n3 - $n4;
                if (isset($map[$temp])) {
                    $count += $map[$temp];
                }
            }
        }
        return $count;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# Swift:

func fourSumCount(_ nums1: [Int], _ nums2: [Int], _ nums3: [Int], _ nums4: [Int]) -> Int {
    // ab sum: ab sum occurrences
    var countDic = [Int: Int]()
    for a in nums1 {
        for b in nums2 {
            let key = a + b
            countDic[key] = countDic[key, default: 0] + 1
        }
    }

    // Use -(c + d) as the key to accumulate occurrences of ab sum
    var result = 0
    for c in nums3 {
        for d in nums4 {
            let key = -(c + d)
            result += countDic[key, default: 0]
        }
    }
    return result
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Rust:

use std::collections::HashMap;
impl Solution {
    pub fn four_sum_count(nums1: Vec<i32>, nums2: Vec<i32>, nums3: Vec<i32>, nums4: Vec<i32>) -> i32 {
        let mut umap:HashMap<i32, i32> = HashMap::new();
        for num1 in &nums1 {
            for num2 in &nums2 {
                *umap.entry(num1 + num2).or_insert(0) += 1;
            }
        }
        
        let mut count = 0;
        
        for num3 in &nums3 {
            for num4 in &nums4 {
                let target:i32 = - (num3 + num4);
                count += umap.get(&target).unwrap_or(&0);          
            }
        }
        
        count
     }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# Scala:

object Solution {
  // Importing
  import scala.collection.mutable
  def fourSumCount(nums1: Array[Int], nums2: Array[Int], nums3: Array[Int], nums4: Array[Int]): Int = {
    // Define a HashMap, key stores the value, value stores the count of that value
    val map = new mutable.HashMap[Int, Int]()
    // Traverse first two arrays, store all possible sums in the map
    for (i <- nums1.indices) {
      for (j <- nums2.indices) {
        val tmp = nums1(i) + nums2(j)
        // If the value exists, increase its key count; if not, add it
        if (map.contains(tmp)) {
          map.put(tmp, map.get(tmp).get + 1)
        } else {
          map.put(tmp, 1)
        }
      }
    }
    var res = 0 // Result variable
    // Traverse other two arrays
    for (i <- nums3.indices) {
      for (j <- nums4.indices) {
        val tmp = -(nums3(i) + nums4(j))
        // If the value exists in map, increase the result by its count
        if (map.contains(tmp)) {
          res += map.get(tmp).get
        }
      }
    }
    // Return the final result, the keyword return can be omitted
    res
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# C#:

public int FourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
       Dictionary<int, int> dic = new Dictionary<int, int>();
        foreach(var i in nums1){
            foreach(var j in nums2){
                int sum = i + j;
                if(dic.ContainsKey(sum)){
                    dic[sum]++;
                }else{
                    dic.Add(sum, 1);
                }
                
            }
        }
        int res = 0;
         foreach(var a in nums3){
            foreach(var b in nums4){
                int sum = a+b;
                if(dic.TryGetValue(-sum, out var result)){
                    res += result;
                }
            }
        }
        return res;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# C:

// Hash table size
const int HASH_SIZE = 101;

typedef struct node {
    int val;
    int count;
    struct node *next;
} node, *HashMap;

// Insert into hash table
void hash_insert(HashMap hashmap[], int val) {
    int idx = val < 0 ? (-val) % HASH_SIZE : val % HASH_SIZE, count = 0;
    node *p = hashmap[idx];
    while (p->next != NULL) {
        p = p->next;
        if (p->val == val) {
            (p->count)++;
            return;
        }
    }
    node *new = malloc(sizeof(node));
    new->val = val;
    new->count = 1;
    new->next = NULL;
    p->next = new;
    return;
}

// Search in hash table
int hash_search(HashMap hashmap[], int val) {
    int idx = val < 0 ? (-val) % HASH_SIZE : val % HASH_SIZE;
    node *p = hashmap[idx];
    while (p->next != NULL) {
        p = p->next;
        if (p->val == val) return p->count;
    }
    return 0;
}

int fourSumCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* nums3, int nums3Size, int* nums4, int nums4Size){
    // Initialize hash table
    HashMap hashmap[HASH_SIZE];
    for (int i = 0; i < HASH_SIZE; i++) {
        hashmap[i] = malloc(sizeof(node));
        hashmap[i]->next = NULL;
    }
    
    // Count two arrays' sums and their occurrences, store in hash table
    int count = 0, num;
    for (int i = 0; i < nums1Size; i++) {
        for(int j = 0; j < nums2Size; j++) {
            num = - nums1[i] - nums2[j];
            hash_insert(hashmap, num);
        }
    }
    
    // Sum other arrays' elements, check hash table for their count, add to total count
    for (int i = 0; i < nums3Size; i++) {
        for(int j = 0; j < nums4Size; j++) {
            num = nums3[i] + nums4[j];
            count += hash_search(hashmap, num);
        }
    }
    return count;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

# Ruby:

# @param {Integer[]} nums1
# @param {Integer[]} nums2
# @param {Integer[]} nums3
# @param {Integer[]} nums4
# @return {Integer}
# New thought: Same logic as the original leader, the later two-array double loop uses a method call plus a single loop for simplification.
# Breakdown into two two-array sum calculations (store results in two hashes), and find zero sum matches once.
# Divide into two groups of two numbers, calculate sums in each group, store in hash where key is the sum and value is the count.
# Ultimately, traverse both hashes once to find zero sum matching count.
def four_sum_count(nums1, nums2, nums3, nums4)
    num_to_count_1 = two_sum_mapping(nums1, nums2)
    num_to_count_2 = two_sum_mapping(nums3, nums4)

    count_sum = 0

    num_to_count_1.each do |num, count|
        count_sum += num_to_count_2[-num] * count # Check other hash for matching sum, uses default 0 if not found; product gives possible count.
    end

    count_sum
end

def two_sum_mapping(nums1, nums2)
    num_to_count = Hash.new(0)

    nums1.each do |num1|
        nums2.each do |nums2|
            num_to_count[num1 + nums2] += 1 # Count sum occurrences of num1 + nums2
        end
    end

    num_to_count
end

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

← 5. Two Sum 7. Ransom Note →