How do you solve 4Sum on LeetCode?

4Sum (LeetCode #18) can be solved using Brute Force or Optimal Solution (Two Pointers). The optimal approach is Optimal Solution (Two Pointers) with O(n^2) time complexity and O(n) space complexity. Key insight: Sorting the array allows us to use the two-pointer technique effectively, reducing the number of combinations we need to check.

What is the brute force solution for 4Sum?

The brute force approach for 4Sum is Brute Force, with O(n^4) time complexity and O(1) space complexity. The brute force approach involves checking every possible combination of four numbers in the array to see if they sum up to the target. This is straightforward but inefficient for larger arrays. The optimal Optimal Solution (Two Pointers) approach improves this to O(n^2).

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

4Sum uses the following concepts: Array, Two Pointers, Sorting. The recommended patterns to study are: Hash Map, Array, Two Pointers.

What are the interview tips for 4Sum?

When you first see this problem, mention that you will consider both brute force and optimized approaches. Communicate your thought process clearly, especially when transitioning from brute force to the optimal solution. Mention edge cases such as arrays with fewer than four elements or arrays with all identical numbers.

What are common mistakes when solving 4Sum?

Failing to handle duplicates correctly, which can lead to incorrect results. Not sorting the array before applying the two-pointer technique, which is crucial for the algorithm to work.

#18

4Sum

Medium

ArrayTwo PointersSortingHash MapArrayTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

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

💡

Intuition

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

The optimal solution uses sorting and the two-pointer technique to reduce the time complexity significantly. By sorting the array first, we can efficiently find quadruplets that sum to the target by fixing two numbers and using two pointers to find the other two.

⚙️

Algorithm

4 steps

1Step 1: Sort the input array.
2Step 2: Iterate through the array with two nested loops to fix the first two numbers.
3Step 3: Use two pointers to find the remaining two numbers that complete the quadruplet.
4Step 4: Skip duplicates to ensure uniqueness of the quadruplets.

solution.py29 lines

1# Full working Python code with comments
2
3def four_sum(nums, target):
4    nums.sort()
5    n = len(nums)
6    result = set()
7    for i in range(n - 3):
8        for j in range(i + 1, n - 2):
9            left, right = j + 1, n - 1
10            while left < right:
11                total = nums[i] + nums[j] + nums[left] + nums[right]
12                if total == target:
13                    result.add((nums[i], nums[j], nums[left], nums[right]))
14                    left += 1
15                    right -= 1
16                    while left < right and nums[left] == nums[left - 1]:
17                        left += 1
18                    while left < right and nums[right] == nums[right + 1]:
19                        right -= 1
20                elif total < target:
21                    left += 1
22                else:
23                    right -= 1
24        while j + 1 < n - 2 and nums[j] == nums[j + 1]:
25            j += 1
26    return [list(quad) for quad in result]
27
28# Example usage
29print(four_sum([1, 0, -1, 0, -2, 2], 0))

ℹ

Complexity note: The time complexity is O(n^2) due to the two nested loops for the first two numbers and the two-pointer technique for the other two. The space complexity is O(n) because we store unique quadruplets in a set.

1Sorting the array allows us to use the two-pointer technique effectively, reducing the number of combinations we need to check.
2Using a set to store results ensures that we only keep unique quadruplets, which is essential for this problem.

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