Domain 2MediumCORE

4Sum II

We are given four integer arrays A, B, C, and D of equal length N. The goal is to find the number of tuples (i, j, k, l) such that the sum of elements at these indices equals zero: A[i] + B[j] + C[k] + D[l] == 0.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table#Binary Search

454. 4Sum II

Model: qwen3.5:9b
Topics: Hash Table,Binary Search
FAANG asked: 1
Acceptance rate: 54.6%


Problem Breakdown

We are given four integer arrays A, B, C, and D of equal length N. The goal is to find the number of tuples (i, j, k, l) such that the sum of elements at these indices equals zero: A[i] + B[j] + C[k] + D[l] == 0.

Inputs: Four lists (arrays) A, B, C, D. Output: An integer representing the count of valid tuples. Constraints & Edge Cases:

  • N ≤ 500: This is a critical constraint. It suggests an O(N3)O(N^3) or even slightly worse solution might pass in some languages but could be risky; however, standard brute force (O(N4)O(N^4)) will definitely time out. We need something closer to quadratic.
  • Integer Range: Values can be negative and large (up to 2^31). Python handles this natively without overflow concerns, unlike fixed-width integer languages like Java or C++. The range is typically −231-2^{31} to 231−12^{31} - 1.
  • Empty Input: If N=0, the loops won’t execute, returning 0 correctly.
  • Duplicates: Arrays may contain duplicate values; we must count every valid index combination, not just unique value combinations.

Intuition

If I were to solve this naively, I would use four nested loops iterating through indices i, j, k, and l. This checks every possible tuple. The time complexity would be O(N4)O(N^4). With N=500, that’s roughly 62 billion operations (5004500^4), which is far too slow for a typical interview limit (usually ~1 second).

To optimize, I need to reduce the number of iterations. Notice the equation: A[i] + B[j] + C[k] + D[l] = 0. I can rearrange this as (A[i] + B[j]) == -(C[k] + D[l]). This allows me to split the problem into two halves.

Key Insight: I don’t need to iterate through all four arrays simultaneously at once. Instead, I can pre-calculate and store all possible sums from A and B in a hash map (frequency table). Then, for every sum generated by C and D, I check if its negation exists in the stored map. This reduces the complexity significantly because we only need two nested loops per half of the problem.

Approach

  1. Pre-compute Sums: Iterate through arrays A and B using two nested loops. Calculate sum_ab = a + b. Store this sum as a key in a hash map (dictionary), where the value is the frequency count of how many times that specific sum occurs. This takes O(N2)O(N^2) time and space.
  2. Check Complements: Iterate through arrays C and D using two nested loops. Calculate sum_cd = c + d. The target we are looking for in our hash map is -sum_cd (since a+b+c+d=0).
  3. Count Matches: If the target exists in the hash map, add its frequency count to a running total of matches found so far. This step also takes O(N2)O(N^2) time with average O(1)O(1) dictionary lookups.
  4. Return Result: Return the accumulated match count after checking all pairs from C and D.

Complexity Analysis

  • Time Complexity: O(N2)O(N^2). We perform two nested loops over N elements for A/B (generating sums), then another set of nested loops for C/D (checking complements). Dictionary operations are amortized O(1)O(1), so the total is proportional to N×N+N×N=O(N2)N \times N + N \times N = O(N^2).
  • Space Complexity: O(N2)O(N^2). In the worst case, every combination of A and B produces a unique sum. The hash map stores up to N2N^2 entries. Given N=500N=500, this is roughly 250k integers, which fits comfortably within memory limits (a few MBs).

Solution

from typing import List
from collections import defaultdict

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        # Dictionary to store frequency of sums from arrays A and B
        sum_map = defaultdict(int)
        
        n = len(A)
        
        # Step 1: Compute all possible sums for A[i] + B[j]
        # Time Complexity here is O(N^2)
        for a in A:
            for b in B:
                current_sum = a + b
                sum_map[current_sum] += 1
        
        count = 0
        
        # Step 2: Iterate through C and D, checking if -(C[k] + D[l]) exists in map
        # Time Complexity here is O(N^2) with O(1) lookup per pair
        for c in C:
            for d in D:
                target = -(c + d)
                
                # If the complement sum exists, add its frequency to count
                if target in sum_map:
                    count += sum_map[target]
                    
        return count

Edge Cases Handled

  • Empty Arrays: The loops for a in A will not execute if N=0. sum_map remains empty. The second loop also won’t run or finds nothing, returning 0 correctly.
  • No Solution Found: If no combination sums to zero, the check if target in sum_map never triggers (or returns 0), and count stays at 0.
  • Duplicate Values/Indices: The problem asks for tuples of indices (i, j, k, l). By iterating over elements directly rather than unique values, we implicitly handle duplicates correctly because every occurrence in the list is processed individually by the nested loops.
  • Negative Numbers: Python’s integer arithmetic handles negative numbers naturally without overflow issues (unlike fixed-width integers), so -(c + d) works regardless of sign combinations.