💬 Discord
Sign In
NeetCode #201LC-18MediumTwo PointersNC 250
← Back to All Problems

#201 · #18 · 4Sum(四数之和)

📌 Problem Statement & Constraints

Given an array nums and a target, return all unique quadruplets [a, b, c, d] that sum to target. Constraints: 1 <= nums.length <= 200, -10^9 <= nums[i], target <= 10^9.

💡 Core Algorithmic Approaches

  1. Extend the 3Sum template with one more outer loop: sort, fix two indices, then solve a two-sum on the remaining suffix with two pointers.
  2. Deduplicate at every level: the first fixed index, the second fixed index, and both pointers after a hit.
  3. Pruning helps a lot: once nums[i] > target with all values non-negative the remaining loop can break, and range checks can skip hopeless pairs.
  4. The overall complexity is O(n^3), which is 8 * 10^6 for n = 200 -- acceptable.

💻 Benchmark Python3 Implementation

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res = []
        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue                   # dedup the first index
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue               # dedup the second index
                l, r = j + 1, n - 1
                need = target - nums[i] - nums[j]
                while l < r:
                    s = nums[l] + nums[r]
                    if s == need:
                        res.append([nums[i], nums[j], nums[l], nums[r]])
                        l += 1
                        r -= 1
                        while l < r and nums[l] == nums[l - 1]:
                            l += 1
                        while l < r and nums[r] == nums[r + 1]:
                            r -= 1
                    elif s < need:
                        l += 1
                    else:
                        r -= 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^3): two nested loops plus an inner two-pointer scan.
💾 Space Complexity
O(1) extra beyond the output and the sort.

⚠️ Interview Pitfalls & Follow-ups

  • Deduplicating only at the innermost level: repeated quadruplets would still appear, because the same value can be chosen at the outer levels in different ways.
  • Using a hash map for the inner two-sum: it works but reintroduces O(n) space and duplicate handling.
  • Forgetting the j > i + 1 guard: the dedup for the second index must not skip the first valid j.
  • Assuming the answer fits in 32 bits: intermediate sums can reach 4 * 10^9, so 64-bit arithmetic is needed in fixed-width languages. Python is safe.
  • Trying to prune with nums[i] > target: that is only valid when all remaining values are non-negative, which the constraints do not guarantee.