Four Number Sum

Tags

Four Number Sum

Category

Arrays

Difficulty

Hard

Problem Statement

Given an array of distinct integers and a target sum, find all quadruplets (sets of four numbers) in the array that sum up to the target value. The function should return a list of all such quadruplets in no particular order.

Intuition

A brute-force approach checking all combinations of four numbers would be O(n^4). We can do better by reducing the problem: just as two-sum uses a hash map to find pairs, we can precompute pair sums and then look up complementary pairs. By iterating through the array and maintaining a hash table of all pair sums seen so far, we can find quadruplets in O(n^2) average time. The key insight is that we process pairs in a specific order to avoid duplicates — we only add pair sums to the hash table after fully processing each element's right-side pairs.

Approach

  1. Initialize an empty hash map pairSums where each key is a sum and the value is a list of pairs that produce that sum.
  2. Initialize an empty list quadruplets to store results.
  3. Iterate through the array with index i from 0 to n-1: a. For each j from i+1 to n-1, compute currentSum = array[i] + array[j]. b. Compute complement = targetSum - currentSum. c. If complement exists in pairSums, iterate through all pairs stored for that complement and append each pair combined with (array[i], array[j]) to quadruplets. d. After the inner loop completes, go back and for each k from 0 to i-1, add the pair (array[k], array[i]) with sum array[k] + array[i] to pairSums.
  4. Return quadruplets.

Pseudocode

function fourNumberSum(array, targetSum):
    pairSums = {}
    quadruplets = []

    for i from 1 to length(array) - 1:
        for j from i + 1 to length(array) - 1:
            currentSum = array[i] + array[j]
            complement = targetSum - currentSum
            if complement in pairSums:
                for pair in pairSums[complement]:
                    quadruplets.append(pair + [array[i], array[j]])

        for k from 0 to i - 1:
            currentSum = array[k] + array[i]
            if currentSum not in pairSums:
                pairSums[currentSum] = []
            pairSums[currentSum].append([array[k], array[i]])

    return quadruplets

Time & Space Complexity

  • Time: O(n^2) on average, O(n^3) in the worst case. The average case arises because hash table lookups are O(1), and we iterate through all pairs. The worst case occurs when many pairs share the same sum, causing the inner retrieval loop to dominate.
  • Space: O(n^2) for storing all pair sums in the hash map, plus O(n^2) for the output in the worst case.

Key Insights

  • The order of operations is critical: we look up complements before inserting the current element's pairs into the hash map. This prevents using the same element twice and avoids duplicate quadruplets.
  • This is a generalization of the two-sum pattern — instead of mapping single values, we map pair sums.
  • Starting the outer loop at index 1 (not 0) ensures that the "add pairs" step in the second inner loop has valid indices to work with.

Edge Cases

  • Array with fewer than 4 elements: return an empty list.
  • No valid quadruplets exist: return an empty list.
  • Multiple quadruplets sharing elements: all valid combinations must be returned.
  • Negative numbers in the array: the algorithm handles them naturally since it relies on sums and complements.
  • Large target sum or very small target sum: no special handling needed.

Linked mentions