Skip to main content

Hashing

4Sum II Solution In C++/Java/Python/Javascript

Problem Description

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

Examples:

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

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
💡
Try it Yourself First!
This problem is a classic yet engaging challenge of counting sum combinations. The goal is to determine the number of tuples (i, j, k, l) such that the sum of four integer arrays equals zero efficiently. The key lies in using a hash map to store sum frequencies, reducing the problem to a two-sum variant for optimal performance.

Brute Force Approach

Intuition

The brute force approach to solving the 4Sum II problem is straightforward: we check every possible combination of four numbers, one from each array, to see how many times their sum equals zero. The idea is to systematically explore all choices without skipping any possibilities.

We achieve this by using four loops, where each loop picks one number from a different array. For each combination of four numbers, we calculate their sum and check if it equals zero. If it does, we increase our count since we have found a valid combination. This ensures that all possible sets of numbers are considered.

While this method may not be the most efficient, it is easy to understand because it follows a direct approach. By simply iterating through all numbers and checking their sum, we get a clear idea of how to find valid quadruplets.

Approach

Step 1: Initialize a counter
Create a variable count and set it to 0. This will keep track of the number of valid quadruplets where the sum equals zero.

Step 2: Pick the first number using the outer loop
Iterate over the first array (A) using an outer loop. This loop selects one number at a time from the first array.

Step 3: Pick the second number using the second loop
For each number selected from A, use a second loop to pick a number from the second array (B). This loop ensures that every combination of two numbers from A and B is considered.

Step 4: Pick the third number using the third loop
For each pair of numbers chosen from A and B, use a third loop to pick a number from the third array (C). This loop expands the combination to three numbers.

Step 5: Pick the fourth number using the fourth loop
For every triplet of numbers selected from A, B, and C, use a fourth loop to pick a number from the fourth array (D). This ensures all possible sets of four numbers are considered.

Step 6: Check the sum of the quadruplet

Compute the sum of the four selected numbers. If the sum equals zero, increase the count by 1 since this is a valid combination.

Step 7: Return the count
After iterating through all possible quadruplets, return the final value of count, which represents the number of valid quadruplets found.

4Sum II Dry run - Brute Force

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

We'll iterate over all possible combinations of one element from each array and check if their sum equals zero :

  1. Pick first element from nums1:
    • 1 (from nums1)
  3. Pick second element from nums2:
    • -2 (from nums2)
    • -1 (from nums2)
  5. Pick third element from nums3:
    • -1 (from nums3)
    • 2 (from nums3)
  7. Pick fourth element from nums4:
    • 0 (from nums4)
    • 2 (from nums4)

Now, let's calculate the sum for each combination:

  1. (1, -2, -1, 0) => Sum = 1 - 2 - 1 + 0 = -2
  2. (1, -2, -1, 2) => Sum = 1 - 2 - 1 + 2 = 0 (Valid)
  3. (1, -2, 2, 0) => Sum = 1 - 2 + 2 + 0 = 1
  4. (1, -2, 2, 2) => Sum = 1 - 2 + 2 + 2 = 3
  5. (1, -1, -1, 0) => Sum = 1 - 1 - 1 + 0 = -1
  6. (1, -1, -1, 2) => Sum = 1 - 1 - 1 + 2 = 1
  7. (1, -1, 2, 0) => Sum = 1 - 1 + 2 + 0 = 2
  8. (1, -1, 2, 2) => Sum = 1 - 1 + 2 + 2 = 4

Now, move to the next element in nums1:

  1. (2, -2, -1, 0) => Sum = 2 - 2 - 1 + 0 = -1
  2. (2, -2, -1, 2) => Sum = 2 - 2 - 1 + 2 = 1
  3. (2, -2, 2, 0) => Sum = 2 - 2 + 2 + 0 = 2
  4. (2, -2, 2, 2) => Sum = 2 - 2 + 2 + 2 = 4
  5. (2, -1, -1, 0) => Sum = 2 - 1 - 1 + 0 = 0 (Valid)
  6. (2, -1, -1, 2) => Sum = 2 - 1 - 1 + 2 = 2
  7. (2, -1, 2, 0) => Sum = 2 - 1 + 2 + 0 = 3
  8. (2, -1, 2, 2) => Sum = 2 - 1 + 2 + 2 = 5

Valid Quadruplets:

  1. (1, -2, -1, 2)
  2. (2, -1, -1, 0)

Total Count of Valid Quadruplets: 2

4Sum II Code for All Languages - Brute Force
C++ 
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        
        // Initialize count to keep track of valid quadruplets
        int count = 0;
        
        // Brute force: Check all possible quadruplets by using four nested loops
        for (int a : nums1) {
            
            // Loop through nums2 to pick the second number
            for (int b : nums2) {
                
                // Loop through nums3 to pick the third number
                for (int c : nums3) {
                    
                    // Loop through nums4 to pick the fourth number
                    for (int d : nums4) {
                        
                        // Calculate the sum of the four selected numbers
                        int sum = a + b + c + d;
                        
                        // If the sum is zero, we found a valid quadruplet
                        if (sum == 0) {
                            
                            // Increment the count for every valid quadruplet
                            count++;
                        }
                    }
                }
            }
        }
        
        // Return the final count of valid quadruplets
        return count;
    }
};

int main() {
    
    // Declare vectors to store the arrays
    vector<int> nums1, nums2, nums3, nums4;
    int n, val;
    
    // Read input for nums1
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> val;
        nums1.push_back(val);
    }
    
    // Read input for nums2
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> val;
        nums2.push_back(val);
    }
    
    // Read input for nums3
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> val;
        nums3.push_back(val);
    }
    
    // Read input for nums4
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> val;
        nums4.push_back(val);
    }
    
    // Create Solution object to call the fourSumCount method
    Solution sol;
    int result = sol.fourSumCount(nums1, nums2, nums3, nums4);
    
    // Output the result
    cout << result << endl;
    
    return 0;
}

4Sum II Code in Java - Brute Force 
import java.util.*;

public class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        
        // Initialize count to keep track of valid quadruplets
        int count = 0;
        
        // Brute force: Check all possible quadruplets by using four nested loops
        for (int a : nums1) {
            for (int b : nums2) {
                for (int c : nums3) {
                    for (int d : nums4) {
                        // Calculate the sum of the four selected numbers
                        int sum = a + b + c + d;
                        
                        // If the sum is zero, we found a valid quadruplet
                        if (sum == 0) {
                            // Increment the count for every valid quadruplet
                            count++;
                        }
                    }
                }
            }
        }
        
        // Return the final count of valid quadruplets
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Input handling for nums1, nums2, nums3, nums4
        int n = scanner.nextInt();
        int[] nums1 = new int[n];
        for (int i = 0; i < n; i++) {
            nums1[i] = scanner.nextInt();
        }
        
        n = scanner.nextInt();
        int[] nums2 = new int[n];
        for (int i = 0; i < n; i++) {
            nums2[i] = scanner.nextInt();
        }
        
        n = scanner.nextInt();
        int[] nums3 = new int[n];
        for (int i = 0; i < n; i++) {
            nums3[i] = scanner.nextInt();
        }
        
        n = scanner.nextInt();
        int[] nums4 = new int[n];
        for (int i = 0; i < n; i++) {
            nums4[i] = scanner.nextInt();
        }
        
        // Create Solution object to call the fourSumCount method
        Solution sol = new Solution();
        int result = sol.fourSumCount(nums1, nums2, nums3, nums4);
        
        // Output the result
        System.out.println(result);
        
        scanner.close();
    }
}

4Sum II Code in Python - Brute Force 
class Solution:
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        # Initialize count to keep track of valid quadruplets
        count = 0
        
        # Brute force: Check all possible quadruplets by using four nested loops
        for a in nums1:
            for b in nums2:
                for c in nums3:
                    for d in nums4:
                        # Calculate the sum of the four selected numbers
                        if a + b + c + d == 0:
                            # Increment the count for every valid quadruplet
                            count += 1
        
        # Return the final count of valid quadruplets
        return count


# Input handling
n = int(input())
nums1 = list(map(int, input().split()))

n = int(input())
nums2 = list(map(int, input().split()))

n = int(input())
nums3 = list(map(int, input().split()))

n = int(input())
nums4 = list(map(int, input().split()))

# Create Solution object to call the fourSumCount method
sol = Solution()
result = sol.fourSumCount(nums1, nums2, nums3, nums4)

# Output the result
print(result)

4Sum II Code in JavaScript - Brute Force 
class Solution {
    fourSumCount(nums1, nums2, nums3, nums4) {
        // Initialize count to keep track of valid quadruplets
        let count = 0;
        
        // Brute force: Check all possible quadruplets by using four nested loops
        for (let a of nums1) {
            for (let b of nums2) {
                for (let c of nums3) {
                    for (let d of nums4) {
                        // Calculate the sum of the four selected numbers
                        if (a + b + c + d === 0) {
                            // Increment the count for every valid quadruplet
                            count++;
                        }
                    }
                }
            }
        }
        
        // Return the final count of valid quadruplets
        return count;
    }
}

// Input handling in JavaScript
let nums1 = [];
let nums2 = [];
let nums3 = [];
let nums4 = [];

let n = parseInt(prompt());
nums1 = prompt().split(' ').map(Number);

n = parseInt(prompt());
nums2 = prompt().split(' ').map(Number);

n = parseInt(prompt());
nums3 = prompt().split(' ').map(Number);

n = parseInt(prompt());
nums4 = prompt().split(' ').map(Number);

// Create Solution object to call the fourSumCount method
let sol = new Solution();
let result = sol.fourSumCount(nums1, nums2, nums3, nums4);

// Output the result
console.log(result);

Time Complexity : O(n^4)

The time complexity of the brute-force solution is determined by the number of iterations required to check all possible quadruplets (i.e., combinations of four numbers). Since the problem involves four nested loops, and each loop iterates over one of the input arrays, the time complexity is calculated as:

  • For each of the four arrays (nums1, nums2, nums3, and nums4), we iterate through all their elements.
  • If the lengths of nums1, nums2, nums3, and nums4 are n1, n2, n3, and n4 respectively, then the total number of iterations is:
    Time Complexity=O(n1×n2×n3×n4)

If all the arrays have the same length n, then the time complexity simplifies to: O(n^4)
Thus, the brute-force approach is O(n1 × n2 × n3 × n4), where n1, n2, n3, and n4 are the lengths of the input arrays.

Space Complexity : O(1)

Auxiliary Space:
The auxiliary space is the extra space used by the algorithm beyond the input. Since we are only using variables to track the count of quadruplets and no extra data structures (like arrays or hash maps) are used, the auxiliary space complexity is O(1).

Total Space:
Total space accounts for both the input space and the auxiliary space. The space required for storing the input arrays (nums1, nums2, nums3, and nums4) is O(n1 + n2 + n3 + n4), where n1, n2, n3, and n4 are the sizes of the input arrays. Since the algorithm doesn't use additional storage besides the input arrays, the total space complexity is:

Total Space Complexity=O(n1+n2+n3+n4)
If all arrays are of the same length n, the total space complexity simplifies to: O(4n)=O(n)

To improve the brute force solution, we can take inspiration from the 2-Sum problem, where we use a hashmap to store values for quick lookup. By removing one loop and introducing a hashmap, we can reduce the time complexity significantly. Instead of iterating through all four arrays, we store the frequency of elements from the fourth array (nums4) in a hashmap.

Better Approach

Intuition

The optimized approach to solving the 4Sum II problem builds on the brute force method but reduces its complexity by leveraging a hashmap for efficient lookups. Instead of checking every possible combination of four numbers directly, we break the problem into smaller parts. The key idea is to precompute and store the frequency of numbers from the fourth array (nums4) in a hashmap. This allows us to quickly check if the required complement exists for any combination of the first three arrays.

We achieve this by using three loops to iterate through nums1, nums2, and nums3. For each combination of these three numbers, we calculate the required complement -(i + j + k). This complement represents the value needed from nums4 to make the sum of all four numbers equal to zero.

By checking the hashmap, we can determine how many times this complement appears in nums4 and add that count to our result. This eliminates the need for a fourth loop and significantly improves efficiency, as hashmap lookups are performed in O(1) time.

While this method introduces a hashmap, it remains intuitive because it simplifies the problem by breaking it into smaller, manageable steps. By storing and reusing information from one array, we avoid redundant calculations and focus on finding valid quadruplets in a more efficient way. 

Approach

Step 1: Initialize a counter
Create a variable count and set it to 0. This will keep track of the number of valid quadruplets where the sum equals zero.

Step 2: Create a hashmap to store frequencies
Initialize a hashmap (map) to store the frequency of numbers from the fourth array (nums4). This will allow us to quickly look up how many times a specific number appears in nums4.

Step 3: Populate the hashmap with numbers from the fourth array
Iterate over the fourth array (nums4) using a loop. For each number, update its frequency in the hashmap. If the number already exists in the hashmap, increment its count; otherwise, add it to the hashmap with a count of 1.

Step 4: Pick the first number using the outer loop
Iterate over the first array (nums1) using an outer loop. This loop selects one number at a time from nums1.

Step 5: Pick the second number using the second loop
For each number selected from nums1, use a second loop to pick a number from the second array (nums2). This ensures that every combination of two numbers from nums1 and nums2 is considered.

Step 6: Pick the third number using the third loop
For each pair of numbers chosen from nums1 and nums2, use a third loop to pick a number from the third array (nums3). This expands the combination to three numbers.

Step 7: Calculate the required complement and update the count
For every triplet of numbers selected from nums1, nums2, and nums3, calculate the required complement as -(i + j + k). Check if this complement exists in the hashmap. If it does, add the frequency of the complement to the count. This ensures that we count all valid quadruplets efficiently.

Step 8: Return the count
After iterating through all possible triplets and checking the hashmap, return the final value of count, which represents the number of valid quadruplets found.

4Sum II Dry run - Better

Input:

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

Step-by-Step Dry Run:

Initializing the HashMap (map):

  1. The HashMap map will store the frequency of each number in nums4.
  2. Loop through nums4: For l = 0: map.put(0, map.getOrDefault(0, 0) + 1) → map = {0=1}
  3. Initializing the count variable: count = 0 to store the result.

Outer Loops through nums1, nums2, and nums3:

  1. The outer three loops iterate over each combination of i from nums1, j from nums2, and k from nums3.
  2. For each combination, we compute the sum -(i + j + k) and check if this sum exists in the HashMap map.

Loop Iteration Details:
Iteration 1: (i = 1, j = -2, k = -1)

  • i + j + k = 1 + (-2) + (-1) = -2
  • -(i + j + k) = 2
  • We check if 2 exists in the map: Yes, it does with frequency 1.
  • So, count += 1 → count = 1.

Iteration 2: (i = 1, j = -2, k = 2)

  • i + j + k = 1 + (-2) + 2 = 1
  • -(i + j + k) = -1
  • We check if -1 exists in the map: No, it doesn't.
  • So, count += 0 → count = 1.

Iteration 3: (i = 1, j = -1, k = -1)

  • i + j + k = 1 + (-1) + (-1) = -1
  • -(i + j + k) = 1
  • We check if 1 exists in the map: No, it doesn't.
  • So, count += 0 → count = 1.

Iteration 4: (i = 1, j = -1, k = 2)

  • i + j + k = 1 + (-1) + 2 = 2
  • -(i + j + k) = -2
  • We check if -2 exists in the map: No, it doesn't.
  • So, count += 0 → count = 1.

Iteration 5: (i = 2, j = -2, k = -1)

  • i + j + k = 2 + (-2) + (-1) = -1
  • -(i + j + k) = 1
  • We check if 1 exists in the map: No, it doesn't.
  • So, count += 0 → count = 1.

Iteration 6: (i = 2, j = -2, k = 2)

  • i + j + k = 2 + (-2) + 2 = 2
  • -(i + j + k) = -2
  • We check if -2 exists in the map: No, it doesn't.
  • So, count += 0 → count = 1.

Iteration 7: (i = 2, j = -1, k = -1)

  • i + j + k = 2 + (-1) + (-1) = 0
  • -(i + j + k) = 0
  • We check if 0 exists in the map: Yes, it does with frequency 1.
  • So, count += 1 → count = 2.

Iteration 8: (i = 2, j = -1, k = 2)

  • i + j + k = 2 + (-1) + 2 = 3
  • -(i + j + k) = -3
  • We check if -3 exists in the map: No, it doesn't.
  • So, count += 0 → count = 2.

Final Result:
After all iterations, the final value of count is 2.
Thus, the total count of quadruplets is 2.

4Sum II Code for All Languages - Better
C++ 
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        // Step 1: Initialize an empty map to store the frequency of each number in nums4
        unordered_map<int, int> map;
        for (int l : nums4) 
            map[l]++;  // Increment the count of each element in nums4
        
        // Step 2: Initialize a counter variable to store the result
        int count = 0;
        
        // Step 3: Iterate through all combinations of nums1, nums2, and nums3
        for (int i : nums1) {
            for (int j : nums2) {
                for (int k : nums3) {
                    // Step 4: Check if the complement exists in the map
                    count += map[-(i + j + k)]; // If complement exists, add its frequency to count
                }
            }
        }
        
        // Step 5: Return the final count
        return count;
    }
};

int main() {
    Solution solution;
    
    // User input for nums1, nums2, nums3, nums4
    int n1, n2, n3, n4;
    cin >> n1 >> n2 >> n3 >> n4;  // Read sizes of the arrays

    vector<int> nums1(n1), nums2(n2), nums3(n3), nums4(n4);

    // Read elements for nums1, nums2, nums3, nums4
    for (int i = 0; i < n1; ++i)
        cin >> nums1[i];
    for (int i = 0; i < n2; ++i)
        cin >> nums2[i];
    for (int i = 0; i < n3; ++i)
        cin >> nums3[i];
    for (int i = 0; i < n4; ++i)
        cin >> nums4[i];
    
    // Call the function and print the result
    int result = solution.fourSumCount(nums1, nums2, nums3, nums4);
    cout << result << endl;
    
    return 0;
}

4Sum II Code in Java - Better 
import java.util.*;

public class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        // Step 1: Initialize an empty map to store the frequency of each number in nums4
        Map<Integer, Integer> map = new HashMap<>();
        for (int l : nums4)
            map.put(l, map.getOrDefault(l, 0) + 1);  // Increment the count of each element in nums4
        
        // Step 2: Initialize a counter variable to store the result
        int count = 0;
        
        // Step 3: Iterate through all combinations of nums1, nums2, and nums3
        for (int i : nums1) {
            for (int j : nums2) {
                for (int k : nums3) {
                    // Step 4: Check if the complement exists in the map
                    count += map.getOrDefault(-(i + j + k), 0); // If complement exists, add its frequency to count
                }
            }
        }
        
        // Step 5: Return the final count
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Solution solution = new Solution();

        // User input for nums1, nums2, nums3, nums4
        int n1 = scanner.nextInt(), n2 = scanner.nextInt(), n3 = scanner.nextInt(), n4 = scanner.nextInt();
        
        int[] nums1 = new int[n1];
        int[] nums2 = new int[n2];
        int[] nums3 = new int[n3];
        int[] nums4 = new int[n4];
        
        // Read elements for nums1, nums2, nums3, nums4
        for (int i = 0; i < n1; i++) nums1[i] = scanner.nextInt();
        for (int i = 0; i < n2; i++) nums2[i] = scanner.nextInt();
        for (int i = 0; i < n3; i++) nums3[i] = scanner.nextInt();
        for (int i = 0; i < n4; i++) nums4[i] = scanner.nextInt();
        
        // Call the function and print the result
        int result = solution.fourSumCount(nums1, nums2, nums3, nums4);
        System.out.println(result);
    }
}

4Sum II Code in Python - Better 
# Function to sort colors using three-pointer approach
def sortColors(nums):
    start, mid, end = 0, 0, len(nums) - 1

    # Step 2: Traverse the array
    while mid <= end:
        if nums[mid] == 0:
            
            # Step 4: Swap and move pointers for 0s
            nums[start], nums[mid] = nums[mid], nums[start]
            start += 1
            mid += 1
        elif nums[mid] == 1:
            
            # Step 5: Move mid pointer for 1s
            mid += 1
        else:
            
            # Step 6: Swap and move end pointer for 2s
            nums[mid], nums[end] = nums[end], nums[mid]
            end -= 1

# Example usage
# Taking input for the size of the array and its elements
n = int(input())
nums = list(map(int, input().split()))

sortColors(nums)

# Print the sorted array
print(nums)

4Sum II Code in JavaScript - Better 
function fourSumCount(nums1, nums2, nums3, nums4) {
    // Step 1: Initialize an empty map to store the frequency of each number in nums4
    let map = new Map();
    for (let l of nums4) {
        map.set(l, (map.get(l) || 0) + 1);  // Increment the count of each element in nums4
    }
    
    // Step 2: Initialize a counter variable to store the result
    let count = 0;
    
    // Step 3: Iterate through all combinations of nums1, nums2, and nums3
    for (let i of nums1) {
        for (let j of nums2) {
            for (let k of nums3) {
                // Step 4: Check if the complement exists in the map
                count += map.get(-(i + j + k)) || 0;  // If complement exists, add its frequency to count
            }
        }
    }
    
    // Step 5: Return the final count
    return count;
}

// User input
let [n1, n2, n3, n4] = prompt().split(" ").map(Number); // Sizes of nums1, nums2, nums3, nums4

let nums1 = prompt().split(" ").map(Number);  // Elements of nums1
let nums2 = prompt().split(" ").map(Number);  // Elements of nums2
let nums3 = prompt().split(" ").map(Number);  // Elements of nums3
let nums4 = prompt().split(" ").map(Number);  // Elements of nums4

// Call the function and display the result
let result = fourSumCount(nums1, nums2, nums3, nums4);
console.log(result);

Time Complexity: O(N)

Building the HashMap:

  • We loop through all the elements of nums4 once, and for each element, we perform a constant time operation (map.put() in Java or map[l] += 1 in Python/JS).
  • Time complexity for this step is O(n4), where n4 is the size of nums4.

Iterating through the Triplet Combination:

  • We loop through each element of nums1, nums2, and nums3 to form the triplets. For each triplet (i, j, k), we check if the complement -(i + j + k) exists in the HashMap (which is a constant time operation).
  • Time complexity for this step is O(n1 * n2 * n3), where n1, n2, and n3 are the sizes of nums1, nums2, and nums3, respectively.

Thus, the overall time complexity of the solution is the sum of these two steps:

  • Total Time Complexity = O(n4) + O(n1 * n2 * n3)

Space Complexity: O(N)

Auxiliary Space:

  • The auxiliary space is the space used by the HashMap to store the frequencies of the elements from nums4.
    • Since the HashMap stores only unique elements from nums4, the auxiliary space is O(n4), where n4 is the number of unique elements in nums4.

Total Space:

  • Auxiliary space as discussed is O(n4).
  • In addition to the space used for the HashMap, the total space complexity also includes the space used to store the input arrays: nums1, nums2, nums3, and nums4. The space for the input arrays is O(n1 + n2 + n3 + n4), where n1, n2, n3, and n4 are the sizes of the respective input arrays.

Thus, the total space complexity is the sum of:

  • The space for storing the input arrays: O(n1 + n2 + n3 + n4)
  • The auxiliary space for the HashMap: O(n4)

Therefore, the total space complexity is O(n1 + n2 + n3 + n4).

To further optimize, we can extend the hashmap approach by storing sums of pairs from two arrays instead of one. By precomputing all possible sums of pairs from nums3 and nums4 and storing their frequencies in the hashmap, we reduce the nested loops from three to two. Now, for every pair from nums1 and nums2, we simply check if the complement -(i + j) exists in the hashmap.

Optimised Approach

Intuition

The most optimized approach to solving the 4Sum II problem builds on the previous hashmap-based solution but further reduces its complexity by leveraging the sums of pairs from two arrays. Instead of iterating through three arrays and using the hashmap for the fourth, we now precompute all possible sums of pairs from the third and fourth arrays (nums3 and nums4) and store their frequencies in a hashmap. This allows us to efficiently check for valid quadruplets using only two nested loops.

We achieve this by iterating through nums1 and nums2 using two loops. For each pair of numbers from these arrays, we calculate the required complement -(i + j) and check if it exists in the hashmap. If it does, we add the frequency of that complement to our count, as it represents the number of valid pairs from nums3 and nums4 that complete the quadruplet.

This approach not only simplifies the problem by reducing the number of nested loops but also significantly improves performance, making it the most efficient solution for the 4Sum II problem. By breaking the problem into smaller, reusable steps, we ensure that the solution is both intuitive and optimal.

Approach

Step 1: Initialize a counter
Create a variable count and set it to 0. This will keep track of the number of valid quadruplets where the sum equals zero.

Step 2: Create a hashmap to store frequencies
Initialize a hashmap (map) to store the frequency of sums of pairs from nums3 and nums4. This will allow us to quickly look up how many times a specific sum appears.

Step 3: Populate the hashmap with numbers from nums3 and nums4
Iterate over each pair (k, l) from nums3 and nums4 using nested loops. For each pair, compute the sum k + l and store the frequency of this sum in the hashmap. If the sum already exists in the hashmap, increment its count; otherwise, add it with an initial count of 1.

Step 4: Pick the first number using the outer loop
Iterate over the first array (nums1) using an outer loop. This loop selects one number at a time from nums1.

Step 5: Pick the second number using the second loop
For each number selected from nums1, use a second loop to pick a number from the second array (nums2). This ensures that every combination of two numbers from nums1 and nums2 is considered.

Step 6: Calculate the required complement and update the count
For every pair of numbers selected from nums1 and nums2, calculate the required complement as -(i + j). Check if this complement exists in the hashmap. If it does, add the frequency of this complement to count, as it represents the number of valid quadruplets that sum to zero.

Step 7: Return the count
After iterating through all possible pairs of numbers from nums1 and nums2 and checking the hashmap, return the final value of count, which represents the number of valid quadruplets found.

4Sum II Dry Run - Optimised

Input:

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

Step 1: Initialize count
count = 0 (to keep track of the number of valid quadruplets)

Step 2: Create a hashmap map to store sums of pairs from nums3 and nums4
map = {} (empty hashmap)

Step 3: Populate the hashmap with sums of pairs from nums3 and nums4

  • Loop through nums3 and nums4 and compute the sum k + l, then update map:
  • For k = -1 (from nums3) and l = 0 (from nums4), the sum is -1 + 0 = -1.
  • map = {-1: 1} (since -1 occurs once)
  • For k = -1 (from nums3) and l = 2 (from nums4), the sum is -1 + 2 = 1.
  • map = {-1: 1, 1: 1} (since 1 occurs once)
  • For k = 2 (from nums3) and l = 0 (from nums4), the sum is 2 + 0 = 2.
  • map = {-1: 1, 1: 1, 2: 1} (since 2 occurs once)
  • For k = 2 (from nums3) and l = 2 (from nums4), the sum is 2 + 2 = 4.
  • map = {-1: 1, 1: 1, 2: 1, 4: 1} (since 4 occurs once)

Step 4: Pick the first number using the outer loop

For i = 1 (from nums1), loop through nums2:

  • For j = -2 (from nums2), the sum of i + j is 1 + (-2) = -1. We need to find the complement -(i + j) = -(-1) = 1.
  • map.getOrDefault(1, 0) returns 1, so count += 1 → count = 1.
  • For j = -1 (from nums2), the sum of i + j is 1 + (-1) = 0. We need to find the complement -(i + j) = -(0) = 0.
  • map.getOrDefault(0, 0) returns 0, so count remains unchanged → count = 1.

For i = 2 (from nums1), loop through nums2:

  • For j = -2 (from nums2), the sum of i + j is 2 + (-2) = 0. We need to find the complement -(i + j) = -(0) = 0.
  • map.getOrDefault(0, 0) returns 0, so count remains unchanged → count = 1.
  • For j = -1 (from nums2), the sum of i + j is 2 + (-1) = 1. We need to find the complement -(i + j) = -(1) = -1.
  • map.getOrDefault(-1, 0) returns 1, so count += 1 → count = 2.

Step 5: Return the count
After iterating through all possible pairs and checking the hashmap, return the final value of count, which is 2. This represents the number of valid quadruplets found.

Final count = 2.

4Sum II Code for All Languages - Optimised
C++ 
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        // Create a hashmap to store the frequency of sums of pairs from nums3 and nums4
        unordered_map<int, int> map;
        
        // Populate the hashmap with sums of pairs from nums3 and nums4
        for (int k : nums3) {
            for (int l : nums4) {
                map[k + l]++; // Increase the frequency count of the sum (k + l)
            }
        }

        // Initialize a counter to store the number of valid quadruplets
        int count = 0;

        // Loop through all combinations of numbers from nums1 and nums2
        for (int i : nums1) {
            for (int j : nums2) {
                // Calculate the complement for the sum of (i + j)
                int complement = -(i + j);
                
                // Check if the complement exists in the map, if so, add the frequency to the count
                count += map[complement]; // Add the number of times the complement appears
            }
        }

        // Return the final count of quadruplets
        return count;
    }
};

int main() {
    // Read the size of nums1, nums2, nums3, nums4
    int n;
    cin >> n;

    // Initialize the arrays
    vector<int> nums1(n), nums2(n), nums3(n), nums4(n);

    // Read the elements for each of the arrays
    for (int i = 0; i < n; i++) {
        cin >> nums1[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> nums2[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> nums3[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> nums4[i];
    }

    // Create an instance of Solution and call fourSumCount function
    Solution solution;
    int result = solution.fourSumCount(nums1, nums2, nums3, nums4);
    
    // Output the result
    cout << result << endl;

    return 0;
}

4Sum II code in Java - Optimised 
import java.util.*;

public class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        // Create a hashmap to store the frequency of sums of pairs from nums3 and nums4
        Map<Integer, Integer> map = new HashMap<>();
        
        // Populate the hashmap with sums of pairs from nums3 and nums4
        for (int k : nums3) {
            for (int l : nums4) {
                map.put(k + l, map.getOrDefault(k + l, 0) + 1); // Increase the frequency count of the sum (k + l)
            }
        }

        // Initialize a counter to store the number of valid quadruplets
        int count = 0;

        // Loop through all combinations of numbers from nums1 and nums2
        for (int i : nums1) {
            for (int j : nums2) {
                // Calculate the complement for the sum of (i + j)
                int complement = -(i + j);
                
                // Check if the complement exists in the map, if so, add the frequency to the count
                count += map.getOrDefault(complement, 0); // Add the number of times the complement appears
            }
        }

        // Return the final count of quadruplets
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Read the size of nums1, nums2, nums3, nums4
        int n = scanner.nextInt();

        // Initialize the arrays
        int[] nums1 = new int[n];
        int[] nums2 = new int[n];
        int[] nums3 = new int[n];
        int[] nums4 = new int[n];

        // Read the elements for each of the arrays
        for (int i = 0; i < n; i++) {
            nums1[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            nums2[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            nums3[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            nums4[i] = scanner.nextInt();
        }

        // Create an instance of Solution and call fourSumCount function
        Solution solution = new Solution();
        int result = solution.fourSumCount(nums1, nums2, nums3, nums4);
        
        // Output the result
        System.out.println(result);

        scanner.close();
    }
}

4Sum II code in Python - Optimised 
class Solution:
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        # Create a hashmap to store the frequency of sums of pairs from nums3 and nums4
        map = {}
        
        # Populate the hashmap with sums of pairs from nums3 and nums4
        for k in nums3:
            for l in nums4:
                map[k + l] = map.get(k + l, 0) + 1  # Increase the frequency count of the sum (k + l)

        # Initialize a counter to store the number of valid quadruplets
        count = 0

        # Loop through all combinations of numbers from nums1 and nums2
        for i in nums1:
            for j in nums2:
                # Calculate the complement for the sum of (i + j)
                complement = -(i + j)
                
                # Check if the complement exists in the map, if so, add the frequency to the count
                count += map.get(complement, 0)  # Add the number of times the complement appears

        # Return the final count of quadruplets
        return count

# Input reading
n = int(input())

nums1 = list(map(int, input().split()))
nums2 = list(map(int, input().split()))
nums3 = list(map(int, input().split()))
nums4 = list(map(int, input().split()))

# Create an instance of Solution and call fourSumCount function
solution = Solution()
result = solution.fourSumCount(nums1, nums2, nums3, nums4)

# Output the result
print(result)

4Sum II Code in Javascript - Optimised 
class Solution {
    fourSumCount(nums1, nums2, nums3, nums4) {
        // Create a hashmap to store the frequency of sums of pairs from nums3 and nums4
        let map = new Map();
        
        // Populate the hashmap with sums of pairs from nums3 and nums4
        for (let k of nums3) {
            for (let l of nums4) {
                map.set(k + l, (map.get(k + l) || 0) + 1); // Increase the frequency count of the sum (k + l)
            }
        }

        // Initialize a counter to store the number of valid quadruplets
        let count = 0;

        // Loop through all combinations of numbers from nums1 and nums2
        for (let i of nums1) {
            for (let j of nums2) {
                // Calculate the complement for the sum of (i + j)
                let complement = -(i + j);
                
                // Check if the complement exists in the map, if so, add the frequency to the count
                count += map.get(complement) || 0; // Add the number of times the complement appears
            }
        }

        // Return the final count of quadruplets
        return count;
    }
}

// Input reading
let n = parseInt(prompt());

let nums1 = prompt().split(' ').map(Number);
let nums2 = prompt().split(' ').map(Number);
let nums3 = prompt().split(' ').map(Number);
let nums4 = prompt().split(' ').map(Number);

// Create an instance of Solution and call fourSumCount function
let solution = new Solution();
let result = solution.fourSumCount(nums1, nums2, nums3, nums4);

// Output the result
console.log(result);

Time Complexity: O(n2)

Building the Map:
We iterate over nums3 and nums4 to compute all possible sums and store them in the hashmap.
The number of iterations for this part is the product of the lengths of nums3 and nums4, i.e., O(n2) where n is the length of each array (assuming all arrays have the same length).
For each pair (k, l) in nums3 and nums4, we perform a constant-time operation (inserting or updating the hashmap), so this step has a time complexity of O(n2).

Iterating over nums1 and nums2:
We loop through each element of nums1 and nums2, and for each combination of (i, j), we compute the complement -(i + j) and check if it exists in the hashmap.
This requires looping through nums1 and nums2, so the number of iterations here is O(n2), and for each iteration, a constant-time lookup operation is performed in the hashmap. Hence, this step also has a time complexity of O(n2).

Final Time Complexity:
Both steps involve iterating through arrays and performing constant-time operations (map insertions and lookups), so the total time complexity is:O(n2)

Space Complexity: O(N)

Auxiliary Space (Space used by the algorithm excluding the input):

  • The only extra data structure we use is a hashmap to store the sum frequencies of pairs from nums3 and nums4. The number of unique sums that can be stored in this hashmap is at most n2 (since each pair of elements from nums3 and nums4 can produce a unique sum).
  • Therefore, the auxiliary space complexity is:O(n2)

Total Space (Including input arrays):

  • The input arrays nums1, nums2, nums3, and nums4 each require O(n) space, where n is the length of each array.
  • Therefore, the total space complexity, including both the input and auxiliary space, is:O(n2) for the hashmap +O(n) for the input arrays, which gives a total space complexity of: O(n2)

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

4Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that: nums[a] + nums[b] + nums[c] + nums[d] == target

Count Special Quadruplets

Given a 0-indexed integer array nums, return the number of distinct quadruplets (a, b, c, d) such that:
nums[a] + nums[b] + nums[c] == nums[d], and a < b < c < d