How do you solve 4Sum II on LeetCode?

4Sum II (LeetCode #454) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n^2) time complexity and O(n) space complexity. Key insight: Using a HashMap can significantly reduce the time complexity from O(n^4) to O(n^2).

What is the brute force solution for 4Sum II?

The brute force approach for 4Sum II is Brute Force, with O(n^4) time complexity and O(1) space complexity. The brute force approach involves checking every possible combination of elements from the four arrays. This means we will iterate through all four arrays and count how many combinations sum to zero. The optimal Optimal Solution approach improves this to O(n^2).

What algorithm or data structure is used to solve 4Sum II?

4Sum II uses the following concepts: Array, Hash Table. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for 4Sum II?

Always consider if you can reduce nested loops by using data structures like HashMaps. Think about how to break down the problem into smaller parts that can be solved independently. Practice explaining your thought process clearly, as communication is key in interviews.

What are common mistakes when solving 4Sum II?

Not using a HashMap for counting sums, leading to inefficient solutions. Overlooking negative sums when checking for pairs.

#454

4Sum II

Medium

ArrayHash TableHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n^4)	O(n^2)
Space	O(1)	O(n)

💡

Intuition

Time O(n^2)Space O(n)

Instead of checking all combinations directly, we can use a HashMap to store the sums of the first two arrays and then check how many times the negative of these sums appear in the sums of the last two arrays. This reduces the time complexity significantly.

⚙️

Algorithm

5 steps

1Step 1: Create a HashMap to store the sums of all pairs from nums1 and nums2.
2Step 2: Iterate through nums1 and nums2, calculating the sum of each pair and storing the count of each sum in the HashMap.
3Step 3: Initialize a counter to zero.
4Step 4: Iterate through nums3 and nums4, calculating the sum of each pair and checking if the negative of this sum exists in the HashMap. If it does, add the count from the HashMap to the counter.
5Step 5: Return the counter.

solution.py13 lines

1# Full working Python code
2
3def fourSumCount(nums1, nums2, nums3, nums4):
4    from collections import defaultdict
5    sum_count = defaultdict(int)
6    for i in nums1:
7        for j in nums2:
8            sum_count[i + j] += 1
9    count = 0
10    for k in nums3:
11        for l in nums4:
12            count += sum_count[-(k + l)]
13    return count

ℹ

Complexity note: The time complexity is O(n^2) because we are iterating through pairs of elements from the first two arrays, and then through pairs of the last two arrays. The space complexity is O(n) due to the HashMap storing the sums.

1Using a HashMap can significantly reduce the time complexity from O(n^4) to O(n^2).
2Counting pairs instead of individual elements allows for efficient lookups.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.