LeetCode 454: 4Sum II Solution in Python – A Step-by-Step Guide

What Is LeetCode 454: 4Sum II?

In LeetCode 454: 4Sum II, you’re given four integer arrays nums1, nums2, nums3, and nums4, all of length n, and your task is to count how many quadruples (i, j, k, l)—one element from each array—sum to zero. For example, with [1, 2], [-2, -1], [-1, 2], [0, 2], there are 2 quadruples: (1, -2, -1, 2) and (2, -1, -1, 0). It’s like finding all the ways to balance four scales to zero using one weight from each.

Problem Statement

• Input: nums1, nums2, nums3, nums4 (List[int])—four integer arrays.
• Output: int—number of quadruples summing to zero.
• Rules:
• Pick one element from each array.
• Count all (i, j, k, l) where nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0.

Constraints

• n == nums1.length == nums2.length == nums3.length == nums4.length.
• 1 <= n <= 500.
• -2^28 <= nums[i] <= 2^28 - 1.

Examples to Get Us Started

• Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
• Output: 2 (Quadruples: (1,-2,-1,2), (2,-1,-1,0)).
• Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
• Output: 1 (Only (0,0,0,0)).
• Input: nums1 = [1,2], nums2 = [-1,-2], nums3 = [1,2], nums4 = [-1,-2]
• Output: 8 (Multiple combinations).

Understanding the Problem: Balancing the Sums

To solve LeetCode 454: 4Sum II in Python, we need to count quadruples across four arrays that sum to zero. A brute force check of all combinations is O(n⁴)—way too slow for n = 500. The key? Break it into pairs and use a hash map to optimize. We’ll explore:

• Best Solution (Hash Map with Two-Sum Pairing): O(n²) time, O(n²) space—fast and clever.
• Alternative Solution (Brute Force): O(n⁴) time, O(1) space—simple but inefficient.

Let’s dive into the hash map solution—it’s the juggler’s trick we need.

Best Solution: Hash Map with Two-Sum Pairing

Why This Is the Best Solution

The hash map with two-sum pairing is the top pick because it’s O(n²) time and O(n²) space, reducing the problem from four dimensions to two by precomputing sums of pairs. It stores sums from two arrays in a hash map, then checks complements from the other two, counting matches in constant time. It’s like juggling two pairs of balls at once, finding how often their totals balance to zero—efficient and slick!

How It Works

Here’s the strategy:

• Step 1: Use a hash map to store sums of pairs from nums1 and nums2 with their frequencies.
• Step 2: For each pair from nums3 and nums4, compute their sum and look up -(sum) in the map, adding its frequency to the count.
• Step 3: Return the total count.
• Why It Works:
• Splits 4sum into two 2sum problems.
• Hash map makes lookups O(1).

Step-by-Step Example

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

• Step 1: Build Map (nums1 + nums2):
• 1 + (-2) = -1, map = {-1:1}.
• 1 + (-1) = 0, map = {-1:1, 0:1}.
• 2 + (-2) = 0, map = {-1:1, 0:2}.
• 2 + (-1) = 1, map = {-1:1, 0:2, 1:1}.
• Step 2: Check nums3 + nums4:
• -1 + 0 = -1, map[-(-1)] = map[1] = 1, count = 1.
• -1 + 2 = 1, map[-1] = 1, count = 2.
• 2 + 0 = 2, map[-2] = 0, count = 2.
• 2 + 2 = 4, map[-4] = 0, count = 2.
• Result: 2 quadruples.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        # Step 1: Build hash map for sums of nums1 + nums2
        sum_map = {}
        for n1 in nums1:
            for n2 in nums2:
                sum_map[n1 + n2] = sum_map.get(n1 + n2, 0) + 1

        # Step 2: Count quadruples using nums3 + nums4
        count = 0
        for n3 in nums3:
            for n4 in nums4:
                target = -(n3 + n4)
                if target in sum_map:
                    count += sum_map[target]

        return count

• Line 4-7: Build map of sums from nums1 + nums2 (e.g., {0:2, 1:1, -1:1}).
• Line 10-14: For each n3 + n4, look up -(sum) in map, add frequency to count.
• Line 16: Return total.
• Time Complexity: O(n²)—two nested loops twice.
• Space Complexity: O(n²)—hash map size.

It’s like a sum-balancing act with a lookup twist!

Alternative Solution: Brute Force with Four Nested Loops

Why an Alternative Approach?

The brute force method checks all possible quadruples—O(n⁴) time, O(1) space—by iterating through each array fully. It’s slow but dead simple, like juggling all four balls at once and counting every catch that lands at zero. Good for small n or understanding the basics!

How It Works

• Step 1: Four nested loops over each array.
• Step 2: Compute sum for each quadruple, increment count if zero.
• Step 3: Return count.

Step-by-Step Example

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

• Loops:
• (1,-2,-1,2): 1 + (-2) + (-1) + 2 = 0, count = 1.
• (2,-1,-1,0): 2 + (-1) + (-1) + 0 = 0, count = 2.
• Others: non-zero sums.
• Result: 2.

Code for Brute Force

Copy codeclass Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        count = 0
        # Four nested loops
        for n1 in nums1:
            for n2 in nums2:
                for n3 in nums3:
                    for n4 in nums4:
                        if n1 + n2 + n3 + n4 == 0:
                            count += 1
        return count

• Line 4-10: Check all quadruples, count sums = 0.
• Time Complexity: O(n⁴)—four nested loops.
• Space Complexity: O(1)—just a counter.

It’s a slow juggling marathon!

Comparing the Two Solutions

• Hash Map (Best):
• Pros: O(n²), fast, scalable.
• Cons: O(n²) space.
• Brute Force (Alternative):
• Pros: O(n⁴), simple, O(1) space.
• Cons: Impractical for n > 50.

Hash map wins hands down.

Edge Cases and More Examples

• Input: [0], [0], [0], [0] → 1.
• Input: [1], [1], [1], [1] → 0.
• Input: [-1,-1], [-1,1], [-1,1], [1,1] → 4.

Hash map handles all efficiently.

Complexity Recap

• Hash Map: Time O(n²), Space O(n²).
• Brute Force: Time O(n⁴), Space O(1).

Hash map’s the champ.

Key Takeaways

• Hash Map: Pair and conquer.
• Brute Force: Check everything.
• Python Tip: Maps speed sums—see [Python Basics](/python/basics).

Final Thoughts: Juggle Those Sums

LeetCode 454: 4Sum II in Python is a sum-counting juggling act. The hash map solution is your fast trick, while brute force is a slow toss. Want more sum fun? Try LeetCode 1: Two Sum or LeetCode 18: 4Sum. Ready to balance some quadruples? Head to Solve LeetCode 454 on LeetCode and juggle those numbers today—your coding skills are zeroed in!