LeetCode Python/Java/C++/JS  >  Hash Table  >  454. 4Sum II  >  Solved in Java, Python, JavaScript, C#, Ruby, Go, C++  >  GitHub or Repost

    LeetCode link: 454. 4Sum II, difficulty: Medium.

    Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

    • 0 <= i, j, k, l < n
    • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

    Example 1:

    Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]

    Output: 2

    Explanation:

    The two tuples are:

    1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
    2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

    Example 2:

    Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]

    Output: 1

    Constraints:

    • n == nums1.length
    • n == nums2.length
    • n == nums3.length
    • n == nums4.length
    • 1 <= n <= 200
    • -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

    Intuition
    PreviousNext

    Webmaster (Zhang Jian): πŸ‘‹

    Hi everyone! I am Zhang Jian.
    I know the challenge of transitioning from mastering algorithms to actually landing a great job. That's why, in addition to this resource, I personally developed leader.me!

    πŸš€ leader.me is the ultimate all-in-one platform for programmers to build their personal brand, featuring portfolio hosting, resume builders, and integrated blogs.

    Build your programmer brand at leader.me β†’


    1. Because the final requirement is to take one number from each group of numbers, the four groups of numbers can be split into two groups of two.
    2. Count the number of each sum. Use Map to store, key is sum, value is count.
    3. Iterate over nums3 and nums4, if -(num3 + num4) exists in keys of Map, then count is included in the total.

    Step-by-Step Solution

    1. Count the number of each sum. Use Map to store, key is sum, value is count.

      num_to_count = defaultdict(int)

for num1 in nums1:
    for num2 in nums2:
        num_to_count[num1 + num2] += 1

    2. Iterate over nums3 and nums4, if -(num3 + num4) exists in keys of Map, then count is included in the total.

      result = 0

for num3 in nums3:
    for num4 in nums4:
        result += num_to_count[-(num3 + num4)]

return result

    Complexity

    Time complexity

    O(N * N)

    Space complexity

    O(N)

    Solution in languages: Java Python JavaScript C# Ruby Go C++

    Java # 

    class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        var numToCount = new HashMap<Integer, Integer>();

        for (var num1 : nums1) {
            for (var num2 : nums2) {
                numToCount.put(
                    num1 + num2,
                    numToCount.getOrDefault(num1 + num2, 0) + 1
                );
            }
        }

        var result = 0;

        for (var num3 : nums3) {
            for (var num4 : nums4) {
                result += numToCount.getOrDefault(-(num3 + num4), 0);
            }
        }

        return result;
    }
}

    Python # 

    # from collections import defaultdict

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        num_to_count = defaultdict(int)

        for num1 in nums1:
            for num2 in nums2:
                num_to_count[num1 + num2] += 1

        result = 0

        for num3 in nums3:
            for num4 in nums4:
                result += num_to_count[-(num3 + num4)]

        return result

    JavaScript # 

    var fourSumCount = function (nums1, nums2, nums3, nums4) {
  const numToCount = new Map()

  for (const num1 of nums1) {
    for (const num2 of nums2) {
      numToCount.set(num1 + num2, (numToCount.get(num1 + num2) || 0) + 1)
    }
  }

  let result = 0

  for (const num3 of nums3) {
    for (const num4 of nums4) {
      result += numToCount.get(-(num3 + num4)) || 0
    }
  }

  return result
};

    C# # 

    public class Solution
{
    public int FourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4)
    {
        var numToCount = new Dictionary<int, int>();

        foreach (int num1 in nums1)
        {
            foreach (int num2 in nums2)
            {
                numToCount[num1 + num2] = numToCount.GetValueOrDefault(num1 + num2, 0) + 1;
            }
        }

        int result = 0;

        foreach (int num3 in nums3)
        {
            foreach (int num4 in nums4)
            {
                result += numToCount.GetValueOrDefault(-(num3 + num4), 0);
            }
        }

        return result;
    }
}

    Ruby # 

    def four_sum_count(nums1, nums2, nums3, nums4)
  num_to_count = Hash.new(0)

  nums1.each do |num1|
    nums2.each do |num2|
      num_to_count[num1 + num2] += 1
    end
  end

  result = 0

  nums3.each do |num3|
    nums4.each do |num4|
      result += num_to_count[-(num3 + num4)]
    end
  end

  result
end

    Go # 

    func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    // Create map to store sum frequencies from first two arrays
    sumCount := make(map[int]int)

    // Calculate all possible sums from nums1 and nums2
    for _, num1 := range nums1 {
        for _, num2 := range nums2 {
            sumCount[num1 + num2]++
        }
    }

    result := 0
    // Check complementary sums from nums3 and nums4
    for _, num3 := range nums3 {
        for _, num4 := range nums4 {
            // Add count of complementary sum that would make total zero
            result += sumCount[-(num3 + num4)]
        }
    }

    return result
}

    C++ # 

    class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        // Store sum frequencies from first two arrays
        unordered_map<int, int> sumCount;

        // Calculate all possible sums from nums1 and nums2
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                sumCount[num1 + num2]++;
            }
        }

        int result = 0;
        // Check complementary sums from nums3 and nums4
        for (int num3 : nums3) {
            for (int num4 : nums4) {
                // Add occurrences of required complement sum
                result += sumCount[-(num3 + num4)];
            }
        }

        return result;
    }
};
    Solution in languages: Java Python JavaScript C# Ruby Go C++

    Other languages

    Welcome to contribute code to LeetCode.blog GitHub -> 454. 4Sum II. Thanks!
    PreviousNext

    Level Up Your Developer Identity

    πŸš€ While mastering algorithms is key, showcasing your talent is what gets you hired.
    We recommend leader.me β€” the ultimate all-in-one personal branding platform for programmers.

    The All-In-One Career Powerhouse:

    • πŸ“„ Resume, Portfolio & Blog: Integrate your skills, projects, and writing into one stunning site.
    • 🌐 Free Custom Domain: Bind your own personal domain for freeβ€”forever.
    • ✨ Premium Subdomains: Stand out with elite tech handle like name.leader.me.

    Build Your Programmer Brand at leader.me β†’