4Sum II

MEDIUM

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

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²⁸

Approaches

Checkout 3 different approaches to solve 4Sum II. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Four Nested Loops

The most straightforward way to solve the problem is to check every possible combination of one element from each of the four arrays. We can use four nested loops to iterate through all tuples (i, j, k, l) and check if the sum of the corresponding elements is zero. If it is, we increment a counter.

Algorithm

1. Initialize a counter variable count to 0.
1. Use a for loop to iterate through nums1 with index i.
1. Inside, use a nested for loop to iterate through nums2 with index j.
1. Inside, use another nested for loop to iterate through nums3 with index k.
1. Inside, use a final nested for loop to iterate through nums4 with index l.
1. In the innermost loop, check if the sum nums1[i] + nums2[j] + nums3[k] + nums4[l] is equal to 0.
1. If the condition is true, increment the count.
1. After all loops complete, return the final count.

This approach exhaustively checks every single tuple. We initialize a counter variable, count, to zero. The first loop iterates through nums1, the second through nums2, the third through nums3, and the fourth through nums4. Inside the innermost loop, we calculate the sum of the four selected elements. If this sum equals 0, we increment our count. After all loops have finished, count will hold the total number of valid tuples, which we then return. While simple to conceptualize, this method is computationally expensive and not practical for the given constraints.

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int count = 0;
        int n = nums1.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    for (int l = 0; l < n; l++) {
                        if (nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) {
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n^4), as it involves four nested loops, each running `n` times. For n=200, this is approximately 200^4 = 1.6 * 10^9 operations, which is too slow.Space Complexity: O(1), as we only use a few variables to store the count and loop indices, independent of the input size.

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra space (O(1) space complexity).

Cons:

Extremely inefficient due to its O(n^4) time complexity.
Guaranteed to result in a 'Time Limit Exceeded' (TLE) error for the given constraints (n <= 200).

Code Solutions

Checking out 3 solutions in different languages for 4Sum II. Click on different languages to view the code.

class Solution {
public
  int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    int count = 0;

Video Solution

Watch the video walkthrough for 4Sum II

Data Structures:

ArrayHash Table