4Sum | Leetcode 18 | Explained in Python

The LeetCode “4Sum” problem asks you to find all unique quadruplets in an integer array nums such that

nums[a] + nums[b] + nums[c] + nums[d] == target     (where a < b < c < d)

Key details:

• Unique means no duplicate quadruplets in the output, regardless of order inside each four-tuple.
• Elements may contain duplicates, but index positions must be distinct.
• Output quadruplets can appear in any order.

Here’s the [Problem Link] to begin with.

Quick Example

Think of it as the bigger sibling of 2Sum and 3Sum: you still balance numbers to hit a target total, but now with four picks and stricter duplicate handling.

Brute Force Solution (Four Nested Loops)

Intuition and Approach

The most direct route is to try every possible combination of four indices:

1. Loop across indices i < j < k < l.
2. Compute their sum; if it equals target, you found a hit.
3. Sort the quadruplet (to get a canonical form) and store it in a set so duplicates collapse automatically.

The logic is crystal clear, but performance quickly becomes prohibitive: checking every quadruplet is O(n⁴).

Code Implementation

def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
    n = len(nums)
    if n < 4:
        return []
    
    my_set = set()  # set ensures uniqueness

    # try all possible quadruplets
    for i in range(0, n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                for l in range(k + 1, n):
                    total = nums[i] + nums[j] + nums[k] + nums[l]

                    if total == target:              # hit the target
                        temp = [nums[i], nums[j], nums[k], nums[l]]
                        temp.sort()                  # canonical order
                        my_set.add(tuple(temp))      # store as tuple in the set

    # convert each tuple back to list
    result = []
    for ans in my_set:
        result.append(list(ans))

    return result

Code Explanation

• Four nested loops generate each unique index combination exactly once.
• Sorting and a set together erase permutations like [1,0,-1,2] vs [-1,1,0,2].
• Finally, the set of tuples is flattened to a list of lists for the return value.

Dry Run (Tiny Example)

For nums = [2, 2, 2, 2], target = 8:

1. Only one quadruplet exists: indices (0,1,2,3).
2. Sum = 2+2+2+2 = 8 → store (2,2,2,2).
3. After loops end, result = [[2,2,2,2]].

Time and Space Complexity

• Time: O(n⁴) – extremely slow for n > 100.
• Space: Up to O(q) for q unique quadruplets (worst‐case ≈ n⁴/24).

Conclusion

Great for conceptual clarity, terrible for large inputs—so let’s optimize!

Better Solution (Hashing Inside Three Loops)

Intuition and Approach

Fix the first two numbers with an outer-pair (i, j).
Now you need a 2Sum on the remaining suffix that equals target – (nums[i]+nums[j]).

• For each (i, j), walk the rest of the array with index k.
• Maintain a hash set of numbers already seen in this inner loop.
• If the needed fourth = target - (nums[i] + nums[j] + nums[k]) is in the set, you have a quadruplet.
• Again sort and store in a global set to kill duplicates.

This trims one whole loop and crashes runtime down to O(n³).

Code Implementation

def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
    n = len(nums)
    if n < 4:
        return []
    
    my_set = set()  # stores unique quadruplets

    # 👫 fix first two indices
    for i in range(0, n):
        for j in range(i + 1, n):
            hash_set = set()  # tracks needed fourth numbers
            # scan remaining indices for third element
            for k in range(j + 1, n):
                fourth = target - (nums[i] + nums[j] + nums[k])

                if fourth in hash_set:           # found match
                    temp = [nums[i], nums[j], nums[k], fourth]
                    temp.sort()
                    my_set.add(tuple(temp))

                # add current third element for future matches
                hash_set.add(nums[k])

    # convert to required list format
    result = [list(ans) for ans in my_set]
    return result

Code Explanation

• Outer double loop picks a distinct pair.
• Inner loop + hash set solves a 2Sum in linear time on the suffix.
• Each (i, j) gets its own hash_set, avoiding cross-pair contamination.

Dry Run (Mini Input)

nums = [1,1,2,2], target = 6

1. (i=0, j=1) → need two numbers summing to 4.
2. k=2 (nums[k]=2), fourth=2, not in set → add 2.
3. k=3 (nums[k]=2), fourth=2 is in set → store [1,1,2,2].

Time and Space Complexity

• Time: O(n³) – three effective loops.
• Space: O(n) extra for the transient hash_set.

Conclusion

Big improvement over brute force, yet still sluggish for n ≈ 1000. We can push further by sorting and sliding pointers.

Optimal Solution (Sort + Two-Pointer Technique)

Intuition and Approach

1. Sort nums to group duplicates and enable two-pointer sweeps.
2. Pick first two indices (i, j) with nested loops, skipping duplicates.
3. For the remaining sub-array, run two pointers k (left) and l (right).
4. Compare their four-number sum to target and move pointers accordingly:

• Sum < target ➜ increase k to make it larger.
• Sum > target ➜ decrease l to make it smaller.
• Sum == target ➜ record quadruplet, shift both pointers, and skip duplicate values.

This gives O(n³) time but with a tiny constant, plus only O(1) auxiliary space.

Code Implementation

def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
    n = len(nums)
    ans = []
    nums.sort()  # Step 1: sort to simplify duplicates

    # 🚶‍♂️ Step 2: pick first two numbers
    for i in range(0, n):
        if i > 0 and nums[i] == nums[i - 1]:  # skip duplicates for i
            continue

        for j in range(i + 1, n):
            if j > i + 1 and nums[j] == nums[j - 1]:  # skip duplicates for j
                continue

            # Step 3: two-pointer search for remaining two
            k = j + 1               # left pointer
            l = n - 1               # right pointer

            while k < l:
                total = nums[i] + nums[j] + nums[k] + nums[l]

                if total == target:
                    ans.append([nums[i], nums[j], nums[k], nums[l]])
                    k += 1
                    l -= 1

                    # skip duplicate values for k
                    while k < l and nums[k] == nums[k - 1]:
                        k += 1
                    # skip duplicate values for l
                    while l > k and nums[l] == nums[l + 1]:
                        l -= 1

                elif total < target:
                    k += 1           # need a larger sum

                else:
                    l -= 1           # need a smaller sum

    return ans

Code Explanation

• Sorting arranges duplicates consecutively, letting simple pointer checks skip repeats.
• Pointer Dynamics: k moves rightward for larger sums; l moves leftward for smaller.
• Duplicate Guards after each pointer shift guarantee every quadruplet appears only once.

Dry Run (Key Steps)

Sorted nums = [-2, -1, 0, 0, 1, 2], target = 0

Pointers skip duplicates along the way, producing exactly three unique quadruplets.

Time and Space Complexity

• Time: O(n³) (dominated by the double loop × linear scan) with a small constant; plus O(n log n) for the sort.
• Space: O(1) extra (ignoring output list).

Conclusion

Sorting + two pointers is the standard, interview-ready answer: concise, fast in practice, and memory-friendly. Master its duplicate-skipping pattern for perfectly clean results.

Final Thoughts 🎯

• Brute Force (O(n⁴)) – intuitive starter, but rarely acceptable.
• Better (Hash-set, O(n³)) – removes one loop, still heavy.
• Optimal (Sort + Two Pointers, O(n³) with tiny constant) – passes competitive constraints with minimal space.

By climbing this ladder, exhaustive → hashing → pointer squeezing, you’ll gain insight not just into 4Sum but the entire family of k-Sum challenges. Happy algorithm hacking!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.