4Sum II - Practice Coding Problems

4Sum II - Problem

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

Find all combinations of indices where one element from each array sums to zero.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: Two valid tuples: nums1[0]+nums2[0]+nums3[0]+nums4[0] = 1+(-1)+(-1)+1 = 0, and nums1[1]+nums2[1]+nums3[1]+nums4[1] = (-1)+1+1+(-1) = 0

Example 2 — All Zeros

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

› Output: 1

💡 Note: Only one combination possible: 0+0+0+0 = 0

Example 3 — No Valid Combinations

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

› Output: 0

💡 Note: All elements are positive, minimum sum is 1+1+1+1 = 4, cannot equal 0

Constraints

n == nums1.length == nums2.length == nums3.length == nums4.length
1 ≤ n ≤ 200
-2²⁸ ≤ nums1[i], nums2[i], nums3[i], nums4[i] ≤ 2²⁸

Visualization

Tap to expand

Understanding the Visualization

Input

Four arrays of equal length with integers

Process

Find combinations where one element from each array sums to 0

Output

Count of valid 4-tuples

Key Takeaway

🎯 Key Insight: Split into two pairs and use hash map to avoid O(n⁴) brute force

Asked in

f Facebook 45 G Google 38 a Amazon 32 M Microsoft 28

The key insight is to split the 4-sum problem into two 2-sum problems. Store all possible sums from the first two arrays in a hash map, then for each sum from the last two arrays, check if its complement exists in the map. Best approach is Two-Pass Hash Map with Time: O(n²), Space: O(n²).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n⁴)	O(1)	Check all possible combinations of four indices
Two-Pass Hash Map	O(n²)	O(n²)	Split into two pairs and use hash map for efficient lookup

Brute Force — Algorithm Steps

Step 1: Use four nested loops for each array
Step 2: Calculate sum for each combination
Step 3: Count combinations that equal zero

Visualization

Tap to expand

Step-by-Step Walkthrough

Four Nested Loops

Generate all combinations (i,j,k,l)

Sum Check

Calculate nums1[i] + nums2[j] + nums3[k] + nums4[l]

Count Zeros

Increment counter when sum equals 0

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* parseArray(char* line, int* size) {
    int* result = malloc(200 * sizeof(int));
    *size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        result[(*size)++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    return result;
}

int solution(int* nums1, int* nums2, int* nums3, int* nums4, int n) {
    int count = 0;
    
    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;
}

int main() {
    char line[1000];
    int n1, n2, n3, n4;
    
    fgets(line, sizeof(line), stdin);
    int* nums1 = parseArray(line, &n1);
    
    fgets(line, sizeof(line), stdin);
    int* nums2 = parseArray(line, &n2);
    
    fgets(line, sizeof(line), stdin);
    int* nums3 = parseArray(line, &n3);
    
    fgets(line, sizeof(line), stdin);
    int* nums4 = parseArray(line, &n4);
    
    printf("%d\n", solution(nums1, nums2, nums3, nums4, n1));
    
    free(nums1);
    free(nums2);
    free(nums3);
    free(nums4);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n⁴)

Four nested loops each iterating n times

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

125.0K Views

Medium Frequency

~25 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler