medium 4Sum II

Problem Statement

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

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

Examples

Example 1:

• Input: nums1 = [1], nums2 = [-1], nums3 = [0], nums4 = [0]
• Expected Output: 1
• Justification: The one quadruplet that sum up to 0 is:
  • (1, -1, 0, 0)

Example 2:

• Input: nums1 = [0, 1], nums2 = [1, -1], nums3 = [-1, 0], nums4 = [1, -1]
• Expected Output: 4
• Justification: The four quadruplets that sum up to 0 are:
  • (0, 1, 0, -1)
  • (0, -1, 0, 1)
  • (1, -1, -1, 1)
  • (1, 1, -1, -1)

Example 3:

• Input: nums1 = [-1, 3], nums2 = [2, -3], nums3 = [3, 4], nums4 = [-4, -3]
• Expected Output: 3
• Justification: The three quadruplets that sum up to 0 are:
  • (-1, 2, 3, -4)
  • (3, -3, 4, -4)
  • (3, -3, 3, -3)

Solution

To solve this problem, we'll leverage a hash map to efficiently find pairs that sum up to the target value, which is zero in this case. The rationale behind using a hash map is to store the sum of pairs from the first two arrays along with their frequency. This way, we can quickly look up the complement of these sums in the hash map when iterating through pairs from the last two arrays. This approach significantly reduces the time complexity compared to a brute force solution, which checks every possible quadruplet.

The effectiveness of this approach lies in its ability to transform the problem from a four-array problem into two, two-array problems, thereby simplifying the process of finding the target sum. By focusing on sums rather than individual elements, we can more easily identify combinations that meet our criteria, making this method both efficient and scalable for larger input sizes.

Step-by-Step Algorithm

1. Initialize a Hash Map: Create an empty hash map (sumMap) to store the sum of each pair from nums1 and nums2 as keys and their frequency (number of times the sum occurs) as values.

2. Compute Sums of Pairs from nums1 and nums2:

   • Iterate over each element in nums1 using a loop.
   • For each element in nums1, iterate over each element in nums2 using another loop.
   • Calculate the sum of the current elements from nums1 and nums2.
   • Update sumMap with this sum. If the sum already exists as a key in sumMap, increment its value by 1. Otherwise, add the sum as a new key with the value of 1.

3. Count Quadruplets:

   • Initialize a counter (count) to 0. This will track the number of quadruplets that sum to 0.
   • Iterate over each element in nums3 using a loop.
   • For each element in nums3, iterate over each element in nums4 using another loop.
   • For the current elements from nums3 and nums4, calculate the sum that would be needed from nums1 and nums2 for the total four elements to sum to 0. This is the negation of the sum of the current elements from nums3 and nums4.
   • Check if this required sum exists as a key in sumMap. If it does, add the corresponding value (frequency) from sumMap to count.

4. Return Result: Return the count variable, which now contains the total number of quadruplets that sum to 0.

Algorithm Walkthrough

Let's consider the Input: nums1 = [0, 1], nums2 = [1, -1], nums3 = [-1, 0], nums4 = [1, -1].

1. Initialize sumMap: Let's start with an empty hash map.

2. Compute Sums of Pairs from nums1 and nums2:

   • Pair 0 from nums1 with 1 from nums2 to get sum 1. Update sumMap: {1: 1}.
   • Pair 0 from nums1 with -1 from nums2 to get sum -1. Update sumMap: {1: 1, -1: 1}.
   • Pair 1 from nums1 with 1 from nums2 to get sum 2. Update sumMap: {1: 1, -1: 1, 2: 1}.
   • Pair 1 from nums1 with -1 from nums2 to get sum 0. Update sumMap: {1: 1, -1: 1, 2: 1, 0: 1}.

3. Count Quadruplets:

   • Pair -1 from nums3 with 1 from nums4. The required sum from nums1 and nums2 is 0 (since -1 + 1 = 0, we need 0 from nums1 and nums2 to sum to 0). sumMap has 0: 1, so increment count by 1.
   • Pair -1 from nums3 with -1 from nums4. The required sum is 2. sumMap has 2: 1, so increment count by 1.
   • Pair 0 from nums3 with 1 from nums4. The required sum is -1. sumMap has -1: 1, so increment count by 1.
   • Pair 0 from nums3 with -1 from nums4. The required sum is 1. sumMap has 1: 1, so increment count by 1.

4. Return Result: The final count is 4, indicating there are 4 quadruplets across the four arrays that sum to 0.

Code

import java.util.HashMap;
import java.util.Map;

public class Solution {

  // Method to count quadruplets that sum to 0
  public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    Map<Integer, Integer> sumMap = new HashMap<>();
    // Compute all possible sums of pairs from nums1 and nums2 and store in sumMap
    for (int a : nums1) {
      for (int b : nums2) {
        sumMap.put(a + b, sumMap.getOrDefault(a + b, 0) + 1);
      }
    }

    int count = 0;
    // For each pair sum from nums3 and nums4, check if the inverse sum exists in sumMap
    for (int c : nums3) {
      for (int d : nums4) {
        count += sumMap.getOrDefault(-(c + d), 0);
      }
    }

    return count;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    System.out.println(
      solution.fourSumCount(
        new int[] { 1 },
        new int[] { -1 },
        new int[] { 0 },
        new int[] { 0 }
      )
    );

    // Example 2
    System.out.println(
      solution.fourSumCount(
        new int[] { 0, 1 },
        new int[] { 1, -1 },
        new int[] { -1, 0 },
        new int[] { 1, -1 }
      )
    );

    // Example 3
    System.out.println(
      solution.fourSumCount(
        new int[] { -1, 3 },
        new int[] { 2, -3 },
        new int[] { 3, 4 },
        new int[] { -4, -3 }
      )
    );
  }
}

Complexity Analysis

Time Complexity

• Computing Sums of Pairs: The first part of the algorithm involves iterating over two loops to compute the sums of elements from nums1 and nums2, and then from nums3 and nums4. Each pair of arrays involves operations where (n) is the length of the array. Since we do this for two pairs of arrays, the time complexity for this part is .
• Looking Up Sums: The second part involves looking up the negative of these sums in the hash map for pairs from nums3 and nums4. This also results in operations, but the lookup time is on average for hash maps, leading to for this part.

The overall time complexity of the algorithm is therefore .

Space Complexity

• Hash Map Storage: The space complexity is primarily due to the storage of sum frequencies in a hash map. In the worst case, all pair sums are unique, leading to space complexity due to the storage of these sums.

Therefore, the overall space complexity of the algorithm is .