Quadruple sum quartet

You're in an Apple phone screen and the interviewer asks, "Given an array of integers, can you find all unique sets of four numbers that add up to a target?" You've seen Two Sum. You've probably solved Three Sum. But Four Sum ratchets up the difficulty by layering duplicate handling, overflow prevention, and a third nested iteration on top of the two-pointer foundation you already know. This problem, also known as 4Sum on other platforms, is a favorite at companies like Apple, Google, Amazon, and Adobe.

TL;DR

Sort the array. Fix the first two numbers with nested loops, then use two pointers (left and right) to find the remaining pair. Skip duplicates at every level to avoid repeated quadruplets. Cast the sum to long in Java (or equivalent in other languages) to prevent integer overflow. This runs in O(n^3) time and O(n^2) space for the result storage.

Why This Problem Matters

Four Sum sits at the intersection of sorting, two pointers, and careful bookkeeping. It shows up regularly at Apple, Google, and Adobe because it tests whether you can extend a well-known pattern (Two Sum, Three Sum) to a harder variant without losing track of edge cases. If you can solve Four Sum cleanly, you can generalize the approach to any K-Sum problem.

From Two Sum to Four Sum

Before diving into the solution, let's understand how Four Sum builds on simpler problems. The progression is straightforward: each step adds one outer loop.

• Two Sum on a sorted array: one pass with two pointers, O(n).
• Three Sum: fix one element, run Two Sum on the rest, O(n^2).
• Four Sum: fix two elements, run Two Sum on the rest, O(n^3).

The pattern is the same at every level. The only new challenges in Four Sum are handling duplicates at two extra levels and guarding against integer overflow.

Understanding the Problem

Given an array nums of n integers and an integer target, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 ≤ a, b, c, d are distinct indices
• nums[a] + nums[b] + nums[c] + nums[d] == target

Each quadruplet must be sorted in ascending order, and the solution set must not contain duplicate quadruplets.

Example:

fourSum([1, 0, -1, 0, -2, 2], 0) => [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
fourSum([2, 2, 2, 2, 2], 8)      => [[2, 2, 2, 2]]

Edge Cases to Consider

1. Array with fewer than 4 elements: return an empty list immediately.
2. All identical elements: [2, 2, 2, 2, 2] with target 8 should return exactly one quadruplet.
3. All zeros: [0, 0, 0, 0] with target 0.
4. Large values: values near 10^9 can overflow a 32-bit integer when summed.

Solution Approach

The strategy has three parts:

1. Sort the array so duplicates are adjacent and the two-pointer technique works.
2. Two nested loops to fix the first two elements (i and j).
3. Two pointers (left and right) to find the remaining pair.

At every level, skip duplicate values to avoid repeating work and producing duplicate quadruplets.

Walking Through the Example

Let's trace through nums = [1, 0, -1, 0, -2, 2] with target = 0.

After sorting: [-2, -1, 0, 0, 1, 2]

Initial pointer positions (i=0, j=1, left=2, right=5):

The sum is (-2) + (-1) + 0 + 2 = -1, which is less than 0. We move left forward. After several adjustments, we reach our first match.

First match found (i=0, j=1, left=4, right=5):

Sum: (-2) + (-1) + 1 + 2 = 0. We record [-2, -1, 1, 2], skip duplicates, and move both pointers inward.

Second match (i=0, j=2, left=3, right=5):

Sum: (-2) + 0 + 0 + 2 = 0. We record [-2, 0, 0, 2].

Third match (i=1, j=2, left=3, right=4):

Sum: (-1) + 0 + 0 + 1 = 0. We record [-1, 0, 0, 1].

Final result: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]].

Handling Duplicates

Duplicate prevention happens at four points, and it is the trickiest part of this problem:

1. Outer loop (i): if nums[i] == nums[i-1], skip.
2. Second loop (j): if j > i+1 and nums[j] == nums[j-1], skip.
3. Left pointer: after a match, advance past identical values.
4. Right pointer: after a match, retreat past identical values.

Missing any one of these checks will produce duplicate quadruplets in your output.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.*;

public class Solution {
  public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length < 4) {
      return result;
    }

    Arrays.sort(nums);
    int n = nums.length;

    for (int i = 0; i < n - 3; i++) {
      // Skip duplicates for the first pointer
      if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
      }
      for (int j = i + 1; j < n - 2; j++) {
        // Skip duplicates for the second pointer
        if (j > i + 1 && nums[j] == nums[j - 1]) {
          continue;
        }
        int left = j + 1;
        int right = n - 1;

        while (left < right) {
          // Cast to long to prevent integer overflow
          long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
          if (sum == target) {
            result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
            // Skip duplicates for left pointer
            while (left < right && nums[left] == nums[left + 1]) {
              left++;
            }
            // Skip duplicates for right pointer
            while (left < right && nums[right] == nums[right - 1]) {
              right--;
            }
            left++;
            right--;
          } else if (sum < target) {
            left++;
          } else {
            right--;
          }
        }
      }
    }

    return result;
  }
}

Let's break down the critical details:

Why (long) nums[i]? The constraints allow values up to 10^9. Four such values summed as 32-bit integers would overflow. Casting the first operand to long promotes the entire expression to 64-bit arithmetic.

Why skip duplicates after sorting? Sorting places identical values next to each other. If nums[i] == nums[i-1], we've already explored every quadruplet starting with that value. Repeating it would only produce duplicates.

Why move both pointers after a match? Once we find a valid quadruplet, the current left/right combination is recorded. The only way to find a new valid pair is to change at least one of them. Moving both inward (after skipping duplicates) ensures we explore all remaining possibilities without repetition.

Complexity Analysis

Time Complexity: O(n^3)

• Sorting takes O(n log n).
• Two nested loops contribute O(n^2).
• The inner two-pointer scan is O(n) for each (i, j) pair.
• Total: O(n^2) * O(n) = O(n^3), which dominates the sort.

Space Complexity: O(n^2)

The result list can contain at most O(n^2) quadruplets in the worst case (though typically far fewer). The sorting uses O(log n) space for the internal sort stack. Combined, this gives O(n^2) space.

Why Not O(n^2) Time?

A hash-map approach stores all pairwise sums and achieves O(n^2) average time. However, it uses O(n^2) space, and handling duplicates becomes significantly more complex. Most interviewers prefer the sorting-based O(n^3) approach because it is cleaner and easier to reason about during a live interview.

Common Pitfalls

1. Integer overflow: forgetting to cast to long in Java or long long in C++. The sum of four large integers will silently wrap around.

2. Incomplete duplicate skipping: skipping duplicates only on i but not on j, or only after a match but not in the outer loops.

3. Off-by-one in loop bounds: the first loop should run to n-3 (inclusive), the second to n-2. Using n-1 or n wastes iterations and can cause index-out-of-bounds errors.

4. Forgetting the final pointer advance: after skipping duplicates for left and right, you still need left++ and right-- to actually move past the matched values.

Interview Tips

When solving this problem in an interview:

1. Start by mentioning Two Sum and Three Sum. Show you recognize the pattern. "This is a natural extension of Three Sum. I'll add one more outer loop."

2. Sort first, always. Writing the sort immediately signals you know where this is going.

3. Be explicit about overflow. Mention the long cast before the interviewer has to ask about it. This shows awareness of production-grade concerns.

4. Test with duplicates. Walk through [2, 2, 2, 2, 2] with target 8 to show your duplicate-skipping logic works correctly.

5. Know the generalization. If asked "what about K Sum?", explain that you'd use (K-2) nested loops followed by a two-pointer pass, giving O(n^(K-1)) time.

Key Takeaways

• Four Sum extends the Two Sum and Three Sum patterns by adding one more outer loop, giving O(n^3) time after an O(n log n) sort.
• Duplicate prevention at every level (both outer loops and both inner pointers) is the most error-prone part. Sorting makes adjacent duplicates easy to detect with a simple equality check.
• Always cast intermediate sums to a 64-bit type (long in Java, long long in C++, i64 in Rust) when inputs can be large. Silent integer overflow is a subtle bug that passes most test cases but fails edge cases.
• The pattern generalizes cleanly to K-Sum: use (K-2) nested loops and a final two-pointer scan, yielding O(n^(K-1)) time.
• A hash-map approach can achieve O(n^2) average time but at the cost of O(n^2) space and much harder duplicate management. The sorting approach is preferred in interview settings.

Practice Makes Perfect

Once you've mastered Four Sum, try these related problems to solidify your understanding of multi-pointer techniques:

• Two Sum (the foundation for all K-Sum problems)
• Zero Sum Triplet Finder (Three Sum, the direct predecessor)
• Maximize Water Storage Between Lines (another two-pointer classic)
• Find Pair Indices in Sorted Array (two pointers on a sorted array)

This problem and thousands of others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed roles at top tech companies. Whether you're working through Two Sum for the first time or polishing your K-Sum generalization skills, consistent practice is what separates good candidates from great ones.

Solutions in Other Languages

Python

class Solution:
    def four_sum(self, nums, target):
        nums.sort()
        quadruplets = []
        n = len(nums)

        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                left, right = j + 1, n - 1
                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]
                    if total == target:
                        quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif total < target:
                        left += 1
                    else:
                        right -= 1

        return quadruplets

JavaScript

class Solution {
  fourSum(nums, target) {
    nums.sort((a, b) => a - b);
    const quadruplets = [];
    const n = nums.length;

    for (let i = 0; i < n - 3; i++) {
      if (i > 0 && nums[i] === nums[i - 1]) continue;
      for (let j = i + 1; j < n - 2; j++) {
        if (j > i + 1 && nums[j] === nums[j - 1]) continue;
        let left = j + 1;
        let right = n - 1;
        while (left < right) {
          const sum = nums[i] + nums[j] + nums[left] + nums[right];
          if (sum === target) {
            quadruplets.push([nums[i], nums[j], nums[left], nums[right]]);
            while (left < right && nums[left] === nums[left + 1]) left++;
            while (left < right && nums[right] === nums[right - 1]) right--;
            left++;
            right--;
          } else if (sum < target) {
            left++;
          } else {
            right--;
          }
        }
      }
    }

    return quadruplets;
  }
}

TypeScript

class Solution {
  fourSum(nums: number[], target: number): number[][] {
    nums.sort((a, b) => a - b);
    const quadruplets: number[][] = [];
    const n = nums.length;

    for (let i = 0; i < n - 3; i++) {
      if (i > 0 && nums[i] === nums[i - 1]) continue;
      for (let j = i + 1; j < n - 2; j++) {
        if (j > i + 1 && nums[j] === nums[j - 1]) continue;
        let left = j + 1;
        let right = n - 1;
        while (left < right) {
          const sum = nums[i] + nums[j] + nums[left] + nums[right];
          if (sum === target) {
            quadruplets.push([nums[i], nums[j], nums[left], nums[right]]);
            while (left < right && nums[left] === nums[left + 1]) left++;
            while (left < right && nums[right] === nums[right - 1]) right--;
            left++;
            right--;
          } else if (sum < target) {
            left++;
          } else {
            right--;
          }
        }
      }
    }

    return quadruplets;
  }
}

C++

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> fourSum(std::vector<int> &nums, int target) {
        std::vector<std::vector<int>> result;
        if (nums.size() < 4) return result;

        std::sort(nums.begin(), nums.end());

        for (size_t i = 0; i < nums.size() - 3; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (size_t j = i + 1; j < nums.size() - 2; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                size_t left = j + 1;
                size_t right = nums.size() - 1;
                while (left < right) {
                    long long sum = static_cast<long long>(nums[i]) + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        result.push_back({nums[i], nums[j], nums[left], nums[right]});
                        while (left < right && nums[left] == nums[left + 1]) ++left;
                        while (left < right && nums[right] == nums[right - 1]) --right;
                        ++left;
                        --right;
                    } else if (sum < target) {
                        ++left;
                    } else {
                        --right;
                    }
                }
            }
        }

        return result;
    }
};

Scala

class Solution {
  def fourSum(nums: Array[Int], target: Int): List[List[Int]] = {
    val sortedNums = nums.sorted
    val n = sortedNums.length
    var result = List[List[Int]]()

    for (i <- 0 until n - 3) {
      if (i == 0 || (i > 0 && sortedNums(i) != sortedNums(i - 1))) {
        for (j <- i + 1 until n - 2) {
          if (j == i + 1 || (j > i + 1 && sortedNums(j) != sortedNums(j - 1))) {
            var left = j + 1
            var right = n - 1
            while (left < right) {
              val sum = sortedNums(i).toLong + sortedNums(j) + sortedNums(left) + sortedNums(right)
              if (sum == target) {
                result = result :+ List(sortedNums(i), sortedNums(j), sortedNums(left), sortedNums(right))
                while (left < right && sortedNums(left) == sortedNums(left + 1)) left += 1
                while (left < right && sortedNums(right) == sortedNums(right - 1)) right -= 1
                left += 1
                right -= 1
              } else if (sum < target) {
                left += 1
              } else {
                right -= 1
              }
            }
          }
        }
      }
    }
    result
  }
}

Kotlin

class Solution {
    fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        if (nums.size < 4) return result

        nums.sort()
        val n = nums.size

        for (i in 0 until n - 3) {
            if (i > 0 && nums[i] == nums[i - 1]) continue
            for (j in i + 1 until n - 2) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue
                var left = j + 1
                var right = n - 1
                while (left < right) {
                    val sum = nums[i].toLong() + nums[j] + nums[left] + nums[right]
                    if (sum == target.toLong()) {
                        result.add(listOf(nums[i], nums[j], nums[left], nums[right]))
                        while (left < right && nums[left] == nums[left + 1]) left++
                        while (left < right && nums[right] == nums[right - 1]) right--
                        left++
                        right--
                    } else if (sum < target) {
                        left++
                    } else {
                        right--
                    }
                }
            }
        }

        return result
    }
}

Ruby

class Solution
  def four_sum(nums, target)
    result = []
    return result if nums.nil? || nums.length < 4

    nums.sort!
    n = nums.length

    (0...n - 3).each do |i|
      next if i > 0 && nums[i] == nums[i - 1]
      (i + 1...n - 2).each do |j|
        next if j > i + 1 && nums[j] == nums[j - 1]
        left = j + 1
        right = n - 1
        while left < right
          current_sum = nums[i] + nums[j] + nums[left] + nums[right]
          if current_sum == target
            result << [nums[i], nums[j], nums[left], nums[right]]
            left += 1 while left < right && nums[left] == nums[left + 1]
            right -= 1 while left < right && nums[right] == nums[right - 1]
            left += 1
            right -= 1
          elsif current_sum < target
            left += 1
          else
            right -= 1
          end
        end
      end
    end

    result
  end
end

Swift

class Solution {
    func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
        var result: [[Int]] = []
        if nums.count < 4 { return result }

        var nums = nums.sorted()
        let n = nums.count

        for i in 0..<n - 3 {
            if i > 0 && nums[i] == nums[i - 1] { continue }
            for j in i + 1..<n - 2 {
                if j > i + 1 && nums[j] == nums[j - 1] { continue }
                var left = j + 1
                var right = n - 1
                while left < right {
                    let sum = Int64(nums[i]) + Int64(nums[j]) + Int64(nums[left]) + Int64(nums[right])
                    if sum == Int64(target) {
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right && nums[left] == nums[left + 1] { left += 1 }
                        while left < right && nums[right] == nums[right - 1] { right -= 1 }
                        left += 1
                        right -= 1
                    } else if sum < Int64(target) {
                        left += 1
                    } else {
                        right -= 1
                    }
                }
            }
        }

        return result
    }
}

Rust

pub struct Solution;

impl Solution {
    pub fn four_sum(&self, mut nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut result: Vec<Vec<i32>> = Vec::new();
        if nums.len() < 4 { return result; }

        nums.sort();
        let n = nums.len();

        for i in 0..n - 3 {
            if i > 0 && nums[i] == nums[i - 1] { continue; }
            for j in i + 1..n - 2 {
                if j > i + 1 && nums[j] == nums[j - 1] { continue; }
                let mut left = j + 1;
                let mut right = n - 1;
                while left < right {
                    let sum = nums[i] as i64 + nums[j] as i64
                            + nums[left] as i64 + nums[right] as i64;
                    if sum == target as i64 {
                        result.push(vec![nums[i], nums[j], nums[left], nums[right]]);
                        while left < right && nums[left] == nums[left + 1] { left += 1; }
                        while left < right && nums[right] == nums[right - 1] { right -= 1; }
                        left += 1;
                        right -= 1;
                    } else if sum < target as i64 {
                        left += 1;
                    } else {
                        right -= 1;
                    }
                }
            }
        }

        result
    }
}

C#

public class Solution {
    public List<List<int>> FourSum(int[] nums, int target) {
        var result = new List<List<int>>();
        if (nums == null || nums.Length < 4) return result;

        Array.Sort(nums);
        int n = nums.Length;

        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1;
                int right = n - 1;
                while (left < right) {
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        result.Add(new List<int> { nums[i], nums[j], nums[left], nums[right] });
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }

        return result;
    }
}

Dart

class Solution {
  List<List<int>> fourSum(List<int> nums, int target) {
    List<List<int>> result = [];
    if (nums.length < 4) return result;

    nums.sort();
    int n = nums.length;

    for (int i = 0; i < n - 3; i++) {
      if (i > 0 && nums[i] == nums[i - 1]) continue;
      for (int j = i + 1; j < n - 2; j++) {
        if (j > i + 1 && nums[j] == nums[j - 1]) continue;
        int left = j + 1;
        int right = n - 1;
        while (left < right) {
          double sum = nums[i].toDouble() + nums[j] + nums[left] + nums[right];
          if (sum == target) {
            result.add([nums[i], nums[j], nums[left], nums[right]]);
            while (left < right && nums[left] == nums[left + 1]) left++;
            while (left < right && nums[right] == nums[right - 1]) right--;
            left++;
            right--;
          } else if (sum < target) {
            left++;
          } else {
            right--;
          }
        }
      }
    }

    return result;
  }
}

PHP

class Solution {
    public function fourSum(array $nums, int $target): array {
        $result = [];
        if (count($nums) < 4) return $result;

        sort($nums);
        $n = count($nums);

        for ($i = 0; $i < $n - 3; $i++) {
            if ($i > 0 && $nums[$i] === $nums[$i - 1]) continue;
            for ($j = $i + 1; $j < $n - 2; $j++) {
                if ($j > $i + 1 && $nums[$j] === $nums[$j - 1]) continue;
                $left = $j + 1;
                $right = $n - 1;
                while ($left < $right) {
                    $sum = $nums[$i] + $nums[$j] + $nums[$left] + $nums[$right];
                    if ($sum === $target) {
                        $result[] = [$nums[$i], $nums[$j], $nums[$left], $nums[$right]];
                        while ($left < $right && $nums[$left] === $nums[$left + 1]) $left++;
                        while ($left < $right && $nums[$right] === $nums[$right - 1]) $right--;
                        $left++;
                        $right--;
                    } elseif ($sum < $target) {
                        $left++;
                    } else {
                        $right--;
                    }
                }
            }
        }

        return $result;
    }
}