Jobs

Interviews

Discussions

4Sum II

Medium

Asked by:

50 views

Topics:

ArraysTwo PointersDynamic Programming

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²⁸ <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2²⁸

Try coding it in LeetCode

4Sum II

Medium

Asked by:

50 views

Topics:

ArraysTwo PointersDynamic Programming

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²⁸ <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2²⁸

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values within the arrays A, B, C, and D? Are negative numbers allowed?
What should I return if no quadruplet sums to zero?
Are duplicate quadruplets counted multiple times, or should each unique quadruplet that sums to zero be counted only once?
Are the input arrays guaranteed to be of the same length, and what is the maximum possible length of each array?
Is the order of the arrays A, B, C, and D significant? Meaning, does (a + b + c + d) count as a different quadruplet from (b + a + c + d)?

Brute Force Solution

Approach

The goal is to find how many combinations of numbers, one from each of four different groups, add up to zero. The brute force strategy is to try every single possible combination of numbers from the four groups to see if it sums to zero.

Here's how the algorithm would work step-by-step:

Pick one number from the first group.
For that number, pick one number from the second group.
For those two numbers, pick one number from the third group.
For those three numbers, pick one number from the fourth group.
Add all four numbers together.
Check if the sum is equal to zero.
If the sum is zero, count this combination as a valid one.
Repeat this process, going through every possible combination of numbers from the four groups.
Keep track of the total number of combinations that add up to zero.

Code Implementation

def four_sum_brute_force(first_group, second_group, third_group, fourth_group):
    zero_sum_combinations = 0

    # Iterate through all possible combinations
    for first_number in first_group:

        for second_number in second_group:

            for third_number in third_group:

                for fourth_number in fourth_group:
                    # Add the four numbers together
                    current_sum = first_number + second_number + third_number + fourth_number

                    # Check if the sum is equal to zero
                    if current_sum == 0:
                        # Increment counter because we found a match
                        zero_sum_combinations += 1

    return zero_sum_combinations

Big(O) Analysis

Time Complexity

O(n^4) – The provided brute force strategy involves iterating through each of the four input arrays A, B, C, and D. For each element in array A, the algorithm iterates through each element in array B. For each pair (A[i], B[j]), the algorithm iterates through each element in array C, and finally, for each triplet (A[i], B[j], C[k]), it iterates through each element in array D. Since these loops are nested, and assuming each array has n elements, the algorithm performs approximately n * n * n * n operations, making the time complexity O(n^4).

Space Complexity

O(1) – The provided brute force strategy does not utilize any auxiliary data structures like arrays, hash maps, or recursion. It operates by iterating through the input lists using nested loops and summing values directly. The only extra memory used consists of a few integer variables for loop indices and calculating the sum, which takes constant space regardless of the size N of the input lists. Thus, the space complexity is O(1).

Optimal Solution

Approach

The most efficient approach involves pre-calculating sums and leveraging a data structure to quickly find complements. We break down the problem into two smaller subproblems, solving each and then combining the results to reach the final answer. This avoids checking every possible combination of numbers.

Here's how the algorithm would work step-by-step:

First, combine the first two lists. For every possible pair of numbers, one from each list, calculate their sum. Store how many times each unique sum appears.
Next, combine the last two lists in a similar way. Calculate the sum of every possible pair of numbers, one from each list.
For each sum calculated from the last two lists, check if its negative (the 'complement') exists in the sums we calculated from the first two lists.
If the complement exists, it means we found a combination of four numbers (one from each original list) that adds up to zero.
Add the number of times the complement appears in the first two lists to a total count. This represents the total number of zero-sum combinations we found.
Return the total count. This count represents all the possible combinations of numbers from the four lists that sum to zero.

Code Implementation

def four_sum_count(nums1, nums2, nums3, nums4):
    sum_frequency = {}
    count = 0

    # Pre-calculate sums of nums1 and nums2 and store frequency.
    for number_from_nums1 in nums1:
        for number_from_nums2 in nums2:
            current_sum = number_from_nums1 + number_from_nums2
            sum_frequency[current_sum] = sum_frequency.get(current_sum, 0) + 1

    # Now, iterate through nums3 and nums4.
    for number_from_nums3 in nums3:
        for number_from_nums4 in nums4:
            current_sum = number_from_nums3 + number_from_nums4

            # Find the complement to reach zero.
            complement = -current_sum

            # Check how many times the complement exists to find matches.
            if complement in sum_frequency:
                count += sum_frequency[complement]

    return count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm first iterates through nums1 and nums2, calculating the sum of each pair (n*n operations) and storing the sums in a hash map. Then it iterates through nums3 and nums4, calculating the sum of each pair (again n*n operations). For each sum from nums3 and nums4, it performs a lookup in the hash map created from nums1 and nums2 which takes O(1) time on average. Therefore, the overall time complexity is dominated by the nested loops for calculating sums from pairs of arrays, resulting in O(n²).

Space Complexity

O(N^2) – The dominant space usage comes from storing the sums of pairs from the first two lists (nums1 and nums2) in a hash map. In the worst case, all possible pairs produce unique sums. If each list has N elements, there are N^2 possible pairs, resulting in up to N^2 unique sums stored in the hash map. Thus, the auxiliary space used is proportional to N^2, where N is the length of each input list. Therefore, the space complexity is O(N^2).

Edge Cases

Case	How to Handle
All input arrays are empty	The number of quadruplets that sum to zero is zero, so return 0.
Input arrays have different lengths	The algorithm should work regardless of the array lengths as it iterates through all combinations; confirm the code does not assume equal lengths.
Arrays contain large positive/negative numbers that could lead to integer overflow when summing	Use a data type (e.g., long) that can accommodate the potential range of sums to prevent overflow.
All arrays contain only zeros	The number of quadruplets summing to zero will be the product of the array lengths; the algorithm must handle large counts correctly.
No quadruplets sum to zero	The algorithm should correctly return 0 in this case without error.
One or more arrays contain duplicate numbers, leading to multiple identical quadruplets	The algorithm's correctness isn't affected by duplicate numbers, as it's counting distinct combinations of indices that sum to zero.
Very large input arrays leading to memory issues with the hash map	Consider using a more memory-efficient data structure or algorithm if memory becomes a bottleneck.
Combination of extreme boundary values (e.g., a mix of Integer.MAX_VALUE and Integer.MIN_VALUE)	Ensure calculations within the algorithm are robust to handle extreme values and avoid potential overflow/underflow issues.

All input arrays are empty

How to Handle:

The number of quadruplets that sum to zero is zero, so return 0.

Input arrays have different lengths

How to Handle:

The algorithm should work regardless of the array lengths as it iterates through all combinations; confirm the code does not assume equal lengths.

Arrays contain large positive/negative numbers that could lead to integer overflow when summing

How to Handle:

Use a data type (e.g., long) that can accommodate the potential range of sums to prevent overflow.

All arrays contain only zeros

How to Handle:

The number of quadruplets summing to zero will be the product of the array lengths; the algorithm must handle large counts correctly.

No quadruplets sum to zero

How to Handle:

The algorithm should correctly return 0 in this case without error.

One or more arrays contain duplicate numbers, leading to multiple identical quadruplets

How to Handle:

The algorithm's correctness isn't affected by duplicate numbers, as it's counting distinct combinations of indices that sum to zero.

Very large input arrays leading to memory issues with the hash map

How to Handle:

Consider using a more memory-efficient data structure or algorithm if memory becomes a bottleneck.

Combination of extreme boundary values (e.g., a mix of Integer.MAX_VALUE and Integer.MIN_VALUE)

How to Handle:

Ensure calculations within the algorithm are robust to handle extreme values and avoid potential overflow/underflow issues.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values within the arrays A, B, C, and D? Are negative numbers allowed?
What should I return if no quadruplet sums to zero?
Are duplicate quadruplets counted multiple times, or should each unique quadruplet that sums to zero be counted only once?
Are the input arrays guaranteed to be of the same length, and what is the maximum possible length of each array?
Is the order of the arrays A, B, C, and D significant? Meaning, does (a + b + c + d) count as a different quadruplet from (b + a + c + d)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Pick one number from the first group.
For that number, pick one number from the second group.
For those two numbers, pick one number from the third group.
For those three numbers, pick one number from the fourth group.
Add all four numbers together.
Check if the sum is equal to zero.
If the sum is zero, count this combination as a valid one.
Repeat this process, going through every possible combination of numbers from the four groups.
Keep track of the total number of combinations that add up to zero.

Code Implementation

def four_sum_brute_force(first_group, second_group, third_group, fourth_group):
    zero_sum_combinations = 0

    # Iterate through all possible combinations
    for first_number in first_group:

        for second_number in second_group:

            for third_number in third_group:

                for fourth_number in fourth_group:
                    # Add the four numbers together
                    current_sum = first_number + second_number + third_number + fourth_number

                    # Check if the sum is equal to zero
                    if current_sum == 0:
                        # Increment counter because we found a match
                        zero_sum_combinations += 1

    return zero_sum_combinations

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, combine the first two lists. For every possible pair of numbers, one from each list, calculate their sum. Store how many times each unique sum appears.
Next, combine the last two lists in a similar way. Calculate the sum of every possible pair of numbers, one from each list.
For each sum calculated from the last two lists, check if its negative (the 'complement') exists in the sums we calculated from the first two lists.
If the complement exists, it means we found a combination of four numbers (one from each original list) that adds up to zero.
Add the number of times the complement appears in the first two lists to a total count. This represents the total number of zero-sum combinations we found.
Return the total count. This count represents all the possible combinations of numbers from the four lists that sum to zero.

Code Implementation

def four_sum_count(nums1, nums2, nums3, nums4):
    sum_frequency = {}
    count = 0

    # Pre-calculate sums of nums1 and nums2 and store frequency.
    for number_from_nums1 in nums1:
        for number_from_nums2 in nums2:
            current_sum = number_from_nums1 + number_from_nums2
            sum_frequency[current_sum] = sum_frequency.get(current_sum, 0) + 1

    # Now, iterate through nums3 and nums4.
    for number_from_nums3 in nums3:
        for number_from_nums4 in nums4:
            current_sum = number_from_nums3 + number_from_nums4

            # Find the complement to reach zero.
            complement = -current_sum

            # Check how many times the complement exists to find matches.
            if complement in sum_frequency:
                count += sum_frequency[complement]

    return count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
All input arrays are empty	The number of quadruplets that sum to zero is zero, so return 0.
Input arrays have different lengths	The algorithm should work regardless of the array lengths as it iterates through all combinations; confirm the code does not assume equal lengths.
Arrays contain large positive/negative numbers that could lead to integer overflow when summing	Use a data type (e.g., long) that can accommodate the potential range of sums to prevent overflow.
All arrays contain only zeros	The number of quadruplets summing to zero will be the product of the array lengths; the algorithm must handle large counts correctly.
No quadruplets sum to zero	The algorithm should correctly return 0 in this case without error.
One or more arrays contain duplicate numbers, leading to multiple identical quadruplets	The algorithm's correctness isn't affected by duplicate numbers, as it's counting distinct combinations of indices that sum to zero.
Very large input arrays leading to memory issues with the hash map	Consider using a more memory-efficient data structure or algorithm if memory becomes a bottleneck.
Combination of extreme boundary values (e.g., a mix of Integer.MAX_VALUE and Integer.MIN_VALUE)	Ensure calculations within the algorithm are robust to handle extreme values and avoid potential overflow/underflow issues.

All input arrays are empty

How to Handle:

The number of quadruplets that sum to zero is zero, so return 0.

Input arrays have different lengths

How to Handle:

The algorithm should work regardless of the array lengths as it iterates through all combinations; confirm the code does not assume equal lengths.

Arrays contain large positive/negative numbers that could lead to integer overflow when summing

How to Handle:

Use a data type (e.g., long) that can accommodate the potential range of sums to prevent overflow.

All arrays contain only zeros

How to Handle:

The number of quadruplets summing to zero will be the product of the array lengths; the algorithm must handle large counts correctly.

No quadruplets sum to zero

How to Handle:

The algorithm should correctly return 0 in this case without error.

One or more arrays contain duplicate numbers, leading to multiple identical quadruplets

How to Handle:

The algorithm's correctness isn't affected by duplicate numbers, as it's counting distinct combinations of indices that sum to zero.

Very large input arrays leading to memory issues with the hash map

How to Handle:

Consider using a more memory-efficient data structure or algorithm if memory becomes a bottleneck.

Combination of extreme boundary values (e.g., a mix of Integer.MAX_VALUE and Integer.MIN_VALUE)

How to Handle:

Ensure calculations within the algorithm are robust to handle extreme values and avoid potential overflow/underflow issues.