Leetcode 454: 4Sum II

Input: The input consists of four arrays nums1, nums2, nums3, nums4 of length n, where each array contains integers.

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

Constraints:

• 1 <= n <= 200

• -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

Output: Return the number of quadruples (i, j, k, l) such that nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0.

Example: Output: 2

Constraints:

• The result should be the count of all valid quadruples.

Goal: The goal is to efficiently find the number of quadruples whose sum is zero.

Steps:

• 1. Iterate through all possible pairs of sums from nums1 and nums2, and store their results in a hash map.

• 2. Iterate through all pairs of sums from nums3 and nums4, and for each pair, check if the negative of the sum exists in the hash map from step 1.

• 3. Count how many such pairs exist and return the total count.

Goal: The algorithm should efficiently handle the problem within the given constraints.

Steps:

• The algorithm must handle arrays of size n up to 200 efficiently.

Assumptions:

• The arrays nums1, nums2, nums3, and nums4 are all of equal length.

• All values in the arrays are integers.

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

• Explanation: In this case, the two valid quadruples are (0, 0, 0, 1) and (1, 1, 0, 0).

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

• Explanation: Here, the only valid quadruple is (0, 0, 0, 0).

Approach: The approach involves using a hash map to efficiently find and count the valid quadruples.

Observations:

• The problem can be reduced to finding pairs of sums that add up to zero.

• Using a hash map to store pairs of sums will allow us to quickly check if the negative of a given sum exists, reducing the time complexity.

Steps:

• 1. Iterate through all pairs (i, j) from nums1 and nums2, and store the sum in a hash map.

• 2. Iterate through all pairs (k, l) from nums3 and nums4. For each pair, check if the negative sum exists in the hash map.

• 3. For each match, increment the result counter.

Empty Inputs:

• If the arrays are empty, the result should be zero.

Large Inputs:

• The algorithm must handle arrays of size up to 200 efficiently.

Special Values:

• If the sum of four numbers equals zero, it should be counted as a valid quadruple.

Constraints:

• The solution should operate within a time complexity of O(n^2).

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
    int res = 0;
    unordered_map<int, int> mp;
    for(int a : A)
    for(int b : B)
    mp[a+b]++;
    for(int c : C)
    for(int d : D)
    if(mp.count(-c-d)) res+= mp[-c-d];
    return res;
}

1 : Function Definition

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {

Defines the function `fourSumCount` that takes four integer vectors as input and returns the number of valid quadruples where the sum of elements from the arrays is zero.

2 : Variable Initialization

    int res = 0;

Initializes a variable `res` to 0, which will hold the count of valid quadruples.

3 : Map Initialization

    unordered_map<int, int> mp;

Declares an unordered map `mp` that will store the sum of pairs from arrays A and B as keys, and their frequency as values.

4 : Outer Loop (Array A)

    for(int a : A)

Starts a loop that iterates through each element of array `A`.

5 : Inner Loop (Array B)

    for(int b : B)

Starts a nested loop that iterates through each element of array `B` for every element in `A`.

6 : Map Update

    mp[a+b]++;

Adds the sum of `a` and `b` to the map `mp`, incrementing its count. This stores the frequency of each pair sum from arrays `A` and `B`.

7 : Outer Loop (Array C)

    for(int c : C)

Starts a loop that iterates through each element of array `C`.

8 : Inner Loop (Array D)

    for(int d : D)

Starts a nested loop that iterates through each element of array `D` for every element in `C`.

9 : Map Lookup and Update

    if(mp.count(-c-d)) res+= mp[-c-d];

Checks if the negated sum `-c-d` exists in the map `mp`. If it does, it adds the frequency of that sum to `res`, indicating the number of valid quadruples found.

10 : Return Statement

    return res;

Returns the count of valid quadruples stored in `res`.

Best Case: O(n^2)

Average Case: O(n^2)

Worst Case: O(n^2)

Description: The time complexity is O(n^2) because we need to check all pairs of sums from the four arrays.

Best Case: O(n^2)

Worst Case: O(n^2)

Description: The space complexity is O(n^2) due to the storage of pairs of sums in the hash map.

Leetcode 454: 4Sum II

Solution to LeetCode 454: 4Sum II Problem

Explore →