algoadvance

Leetcode 454. 4Sum II

Problem Statement

Given four lists A, B, C, and D of integer values, compute how many tuples (i, j, k, l) there are such that:

To clarify, you need to find the number of distinct tuples that sum up to zero where each element of the tuple comes from one of the four lists.

Clarifying Questions

  1. Input Size: What is the length of each list?
  2. Range of Elements: What are the possible values for the elements in each list?
  3. Duplicates: Are there duplicate values within each list, and can they be used multiple times in different tuples?
  4. Output Format: Should we return the count of such tuples?

Example

Given:

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

Output:

2

Explanation: The tuples are (0, 0, 0, 1) and (1, 1, 0, 0).

Strategy

We’ll employ a hashmap (unordered_map) to count how often each sum of pairs from lists A and B appears. Then, we’ll iterate over pairs from lists C and D to check how many pairs match with the required sum to reach zero.

  1. Create a hash map to store (A[i] + B[j]) and their counts.
  2. Iterate through each pair from lists C and D and check if the negation of their sum exists in the hash map.
  3. Sum the counts from the hash map for valid tuples.

This way, rather than using a brute force algorithm which would be O(n^4), we reduce it to O(n^2) in terms of both time and space complexity.

Code

#include <vector>
#include <unordered_map>

class Solution {
public:
    int fourSumCount(std::vector<int>& A, std::vector<int>& B, std::vector<int>& C, std::vector<int>& D) {
        std::unordered_map<int, int> sumAB;
        
        // Store sums of pairs from A and B
        for (int a : A) {
            for (int b : B) {
                sumAB[a + b]++;
            }
        }
        
        int count = 0;
        
        // Find complements in pairs from C and D
        for (int c : C) {
            for (int d : D) {
                int target = -(c + d);
                if (sumAB.find(target) != sumAB.end()) {
                    count += sumAB[target];
                }
            }
        }
        return count;
    }
};

Time Complexity

Space Complexity

This approach effectively balances between time and space efficiency to handle the problem within reasonable limits.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI