Domain 2MediumCORE

4Sum

We are given an array of integers nums and a target integer value. The goal is to find all unique quadruplets (groups of four numbers) within that array where their sum equals the target.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Hash Table#Two Pointers

18. 4Sum

Model: qwen3.5:9b
Topics: Array,Hash Table,Two Pointers
FAANG asked: 1
Acceptance rate: 35.1%


Problem Breakdown

We are given an array of integers nums and a target integer value. The goal is to find all unique quadruplets (groups of four numbers) within that array where their sum equals the target.

Key constraints to note:

  1. Uniqueness: The solution set must not contain duplicate quadruplets. If [a, b, c, d] sums correctly, we cannot return [-2, -1, 0, 3] if that same combination appears again in a different order or via duplicates from the input array (e.g., multiple zeros).
  2. Input Size: NN is up to 200. This suggests an algorithm better than brute force (O(N4)O(N^4)) but allows for something like O(N3)O(N^3).
  3. Values: Integers can be negative and large, so we must handle arithmetic carefully (though Python handles arbitrary precision integers automatically).

Intuition

A naive approach would use four nested loops to check every combination of indices (i,j,k,l)(i, j, k, l) where i<j<k<li < j < k < l. This results in a time complexity of O(N4)O(N^4). Given the constraint N≤200N \le 200, while technically feasible (1616 billion operations is too high for typical limits), we can optimize significantly.

The core insight comes from reducing this to a Two Sum problem: If we fix two numbers, say nums[i] and nums[j], the remaining task becomes finding two other numbers that sum up to (target - nums[i] - nums[j]). This is exactly what the Two Pointers technique solves efficiently on a sorted array.

To handle duplicates effectively (which are required for uniqueness), we should sort the input array first. Sorting allows us to easily skip over identical values during iteration, ensuring we don’t generate duplicate quadruplets in our result set.

Approach

  1. Sort: Sort nums initially (O(Nlog⁡N)O(N \log N)). This enables two-pointer logic and easy duplicate skipping.
  2. Outer Loop (First Number): Iterate through the array with index i.
    • Skip if we are at a value equal to the previous one (nums[i] == nums[i-1]) to avoid duplicates for this position.
  3. Inner Logic: For each valid i, initialize two pointers, left (at i + 1) and right (at end of array).
  4. Two Pointers Loop: While left < right:
    • Calculate current sum: nums[i] + nums[left] + nums[right]. Note that we need a second loop or logic to pick the second number? Actually, standard optimization for kk-Sum is fixing one index and using two pointers on the rest. Wait, 4-Sum requires picking two numbers from the remaining subarray.
    • Correction: The approach isn’t just “fix i”. We need to fix i (first number) AND then find pairs in the remainder? No, that’s O(N3)O(N^3) logic where we iterate j as well.
    • Refined Approach: Fix index i. Then use two pointers (left, right) on the subarray [i+1...end] to solve for 2 numbers summing to remainder? No, that solves a+b+c+da+b+c+d. If we fix nums[i], we still need three more.
    • Correct Logic: Fix index i. Then iterate with a second pointer (or implicitly via two pointers) on the rest of array?
    • Actually, standard 4Sum is: Iterate i from 00 to N−3N-3. Inside that, use Two Pointers for indices left, right in range [i+1, N-1]. Wait, if we fix nums[i], we need three more numbers. That’s not a standard 2-pointer problem (which finds two numbers).
    • Wait, the prompt asks for a+b+c+da+b+c+d. If I sort and iterate index i as the first number, then I have to find two other numbers from the remaining array? No, that would be finding pairs.
    • Let’s re-evaluate: To get 4Sum in O(N3)O(N^3), we usually fix two indices (ii and jj) or iterate i (first number), then use two pointers to find the remaining three? No, that doesn’t work directly.
    • Standard Solution Pattern for K-Sum:
      1. Sort array.
      2. Loop index i from 00 to N−4N-4. Skip duplicates of nums[i].
      3. Inside loop i, use Two Pointers (left = i+1, right = N-1) on the remaining subarray? No, that only finds one pair summing to remainder if we treat it as a+b+c+da+b+c+d.

Python Solution (Two-Pointers with Early Pruning)

class Solution:
    def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
        nums.sort()
        n = len(nums)
        ans = []

        for i in range(n - 3):
            # Avoid duplicate quadruplets for the first element
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            # Early pruning: minimum possible sum is too large
            if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
                break
            
            # Early pruning: maximum possible sum with nums[i] is too small
            if nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target:
                continue

            for j in range(i + 1, n - 2):
                # Avoid duplicate quadruplets for the second element
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                
                # Early pruning for the second loop
                if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
                    break
                if nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target:
                    continue

                left, right = j + 1, n - 1

                while left < right:
                    curr_sum = nums[i] + nums[j] + nums[left] + nums[right]

                    if curr_sum == target:
                        ans.append([nums[i], nums[j], nums[left], nums[right]])
                        left += 1
                        right -= 1

                        # Skip duplicates for third and fourth elements
                        while left < right and nums[left] == nums[left - 1]:
                            left += 1
                        while left < right and nums[right] == nums[right + 1]:
                            right -= 1

                    elif curr_sum < target:
                        left += 1
                    else:
                        right -= 1

        return ans

Key Techniques

  1. Sorting & Two Pointers: Sorting simplifies finding duplicate elements and allows us to use two outer loops (ii and jj) along with a two-pointer approach (left and right) for the inner sum, reducing time complexity to O(n3)O(n^3).
  2. Duplicate Skipping: To prevent duplicate quadruplets in the answer:
  • Skip nums[i] if nums[i] == nums[i - 1].
  • Skip nums[j] if nums[j] == nums[j - 1].
  • Advance left and right past identical numbers after finding a valid quadruplet.
  1. Early Pruning (Optimization): Checking the theoretical minimum and maximum sums for i and j at each step allows skipping iterations that cannot produce target, making execution significantly faster.

Complexity

  • Time Complexity: O(n3)O(n^3) — two nested loops over an O(n)O(n) two-pointer search.
  • Space Complexity: O(1)O(1) additional space (excluding the output list and sorting space).