Four Sum Problem All Unique Quadruplets in DSA Java

Mental Model

Find four numbers in a list that add up to a target sum without repeating quadruplets.

Analogy: Imagine picking four different fruits from a basket so their total weight matches a target weight exactly, and you never pick the same combination twice.

Array: [1, 0, -1, 0, -2, 2]
Indices:  0  1   2  3   4  5
Goal: Find quadruplets that sum to 0

Dry Run Walkthrough

Input: list: [1, 0, -1, 0, -2, 2], target: 0

Goal: Find all unique sets of four numbers that add up to 0

Step 1: Sort the array to make it easier to find quadruplets

[-2, -1, 0, 0, 1, 2]

Why: Sorting helps avoid duplicates and use two-pointer technique

Step 2: Fix first number at index 0 (-2), then fix second number at index 1 (-1)

[-2, -1, 0, 0, 1, 2]

Why: Start exploring quadruplets by fixing first two numbers

Step 3: Use two pointers: left=2 (0), right=5 (2), sum = -2 + -1 + 0 + 2 = -1 < 0, move left pointer right

[-2, -1, 0, 0, 1, 2] left=3(0), right=5(2)

Why: Sum less than target, increase sum by moving left pointer

Step 4: Sum = -2 + -1 + 0 + 2 = -1 < 0, move left pointer right again

[-2, -1, 0, 0, 1, 2] left=4(1), right=5(2)

Why: Still less than target, move left pointer to increase sum

Step 5: Sum = -2 + -1 + 1 + 2 = 0, quadruplet found: [-2, -1, 1, 2], move both pointers to avoid duplicates

[-2, -1, 0, 0, 1, 2] left=5, right=4 (pointers crossed)

Why: Found valid quadruplet, move pointers to find new combinations

Step 6: Fix second number at index 2 (0), left=3 (0), right=5 (2), sum = -2 + 0 + 0 + 2 = 0, quadruplet found: [-2, 0, 0, 2]

[-2, -1, 0, 0, 1, 2]

Why: Found another quadruplet with different second number

Step 7: Fix first number at index 1 (-1), second number at index 2 (0), left=3 (0), right=5 (2), sum = -1 + 0 + 0 + 2 = 1 > 0, move right pointer left

[-2, -1, 0, 0, 1, 2] left=3(0), right=4(1)

Why: Sum too big, decrease sum by moving right pointer

Step 8: Sum = -1 + 0 + 0 + 1 = 0, quadruplet found: [-1, 0, 0, 1]

[-2, -1, 0, 0, 1, 2]

Why: Found last unique quadruplet

Result:

[-2, -1, 1, 2]
[-2, 0, 0, 2]
[-1, 0, 0, 1]

Annotated Code

DSA Java

import java.util.*;

public class FourSum {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // sort array to use two pointers and avoid duplicates
        int n = nums.length;
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates for first number
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // skip duplicates for second number
                int left = j + 1;
                int right = n - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) left++; // skip duplicates
                        while (left < right && nums[right] == nums[right + 1]) right--; // skip duplicates
                    } else if (sum < target) {
                        left++; // increase sum
                    } else {
                        right--; // decrease sum
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> quadruplets = fourSum(nums, target);
        for (List<Integer> quad : quadruplets) {
            System.out.println(quad.get(0) + ", " + quad.get(1) + ", " + quad.get(2) + ", " + quad.get(3));
        }
    }
}

Arrays.sort(nums); // sort array to use two pointers and avoid duplicates

sort array to enable two-pointer technique and skip duplicates

if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates for first number

skip repeated first numbers to avoid duplicate quadruplets

if (j > i + 1 && nums[j] == nums[j - 1]) continue; // skip duplicates for second number

skip repeated second numbers to avoid duplicate quadruplets

while (left < right) { int sum = nums[i] + nums[j] + nums[left] + nums[right]; ... }

use two pointers to find pairs that complete quadruplet sum

if (sum == target) { result.add(...); left++; right--; while (...) left++; while (...) right--; }

found quadruplet, add to result and move pointers skipping duplicates

else if (sum < target) { left++; } else { right--; }

adjust pointers to increase or decrease sum towards target

Output

-2, -1, 1, 2

-2, 0, 0, 2

-1, 0, 0, 1

Complexity Analysis

Time: O(n^3) because we use three nested loops and a two-pointer scan inside

Space: O(k) where k is number of quadruplets found, for storing results

vs Alternative: Better than naive O(n^4) approach that checks all quadruplets by brute force

Edge Cases

Empty array

Returns empty list, no quadruplets found

DSA Java

for (int i = 0; i < n - 3; i++) { ... }

Array with fewer than 4 elements

Returns empty list, no quadruplets possible

DSA Java

for (int i = 0; i < n - 3; i++) { ... }

All elements are the same and sum matches target

Returns one quadruplet with those elements, duplicates skipped

DSA Java

if (i > 0 && nums[i] == nums[i - 1]) continue;

When to Use This Pattern

When asked to find unique quadruplets summing to a target, use sorting plus two nested loops and two pointers to efficiently find all sets without duplicates.

Common Mistakes

Mistake: Not sorting the array before processing, causing difficulty skipping duplicates
Fix: Always sort the array first to enable two-pointer technique and duplicate skipping

Mistake: Not skipping duplicates for first and second numbers, leading to repeated quadruplets
Fix: Add checks to skip repeated values for i and j indices

Mistake: Not moving pointers correctly after finding a quadruplet, causing infinite loops or duplicates
Fix: After finding a quadruplet, move both pointers and skip duplicates carefully

Summary

Finds all unique sets of four numbers in an array that add up to a target sum.

Use when you need to find quadruplets with a specific sum without duplicates.

Sort the array and use two nested loops plus two pointers to efficiently find quadruplets and skip duplicates.

Practice

1. What is the main goal of the Four Sum Problem in data structures and algorithms?

easy

A. Find all unique quadruplets in an array that sum up to a target value

B. Sort the array in ascending order

C. Find the maximum element in the array

D. Count the number of pairs that sum to a target

Solution

1. Step 1: Understand the problem statement

   The Four Sum Problem asks to find sets of four numbers in an array that add up to a given target.

2. Step 2: Identify the expected output

   We want all unique quadruplets, meaning no repeated sets, that sum exactly to the target.

3. Final Answer:

   Find all unique quadruplets in an array that sum up to a target value -> Option A

4. Quick Check:

   Four Sum = unique quadruplets summing to target [OK]

Hint: Look for four numbers adding to target without duplicates [OK]

Common Mistakes:

• Confusing Four Sum with Two Sum or Three Sum problems
• Ignoring uniqueness of quadruplets
• Trying to find maximum or minimum instead of sum

2. Which of the following Java code snippets correctly initializes an empty list to store quadruplets for the Four Sum problem?

easy

A. List quadruplets = new List<>();

B. List quadruplets = new ArrayList<>();

C. ArrayList<int> quadruplets = new ArrayList<>();

D. List<List> quadruplets = new ArrayList();

Solution

1. Step 1: Check Java syntax for list initialization

   Correct generic syntax for a list of lists of integers is List quadruplets = new ArrayList<>();

2. Step 2: Identify errors in other options

   List quadruplets = new List<>(); uses raw List without generics and wrong constructor; ArrayList<int> quadruplets = new ArrayList<>(); uses primitive int which is invalid; List<List> quadruplets = new ArrayList(); mixes generics incorrectly.

3. Final Answer:

   List quadruplets = new ArrayList<>(); -> Option B

4. Quick Check:

   Correct generic list initialization = List quadruplets = new ArrayList<>(); [OK]

Hint: Use List with ArrayList constructor [OK]

Common Mistakes:

• Using raw types without generics
• Trying to use primitive types in generics
• Incorrect constructor calls for List

3. What will be the output of the following Java code snippet for the Four Sum problem?

int[] nums = {1, 0, -1, 0, -2, 2};
int target = 0;
List result = fourSum(nums, target);
System.out.println(result);

Assuming fourSum correctly finds all unique quadruplets summing to target.

medium

A. [[-2, -1, 0, 1], [0, 0, 0, 0]]

B. [[1, 0, -1, 0]]

C. [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

D. []

Solution

1. Step 1: Sort and find quadruplets summing to zero

   Sorted array: [-2, -1, 0, 0, 1, 2]. Quadruplets summing to 0 are [-2,-1,1,2], [-2,0,0,2], and [-1,0,0,1].

2. Step 2: Verify uniqueness and completeness

   All quadruplets are unique and sum exactly to target 0. No other quadruplets exist.

3. Final Answer:

   [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] -> Option C

4. Quick Check:

   Unique quadruplets sum to 0 = [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] [OK]

Hint: Sort array first, then find quadruplets with two pointers [OK]

Common Mistakes:

• Not sorting array before processing
• Including duplicate quadruplets
• Missing some valid quadruplets

4. Identify the bug in this Java snippet for the Four Sum problem:

for (int i = 0; i < nums.length - 3; i++) {
  for (int j = i + 1; j < nums.length - 2; j++) {
    int left = j + 1, right = nums.length - 1;
    while (left < right) {
      int sum = nums[i] + nums[j] + nums[left] + nums[right];
      if (sum == target) {
        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
        left++;
        right--;
      } else if (sum < target) {
        left++;
      } else {
        right--;
      }
    }
  }
}

medium

A. Sum calculation uses wrong indices

B. Incorrect initialization of left and right pointers

C. Wrong loop conditions for i and j

D. Missing checks to skip duplicate elements for i, j, left, and right

Solution

1. Step 1: Analyze loop and pointer usage

   Loops and pointers are correctly set to find quadruplets, and sum calculation is correct.

2. Step 2: Identify missing duplicate skipping

   Code lacks checks to skip duplicate values for i, j, left, and right after finding a quadruplet, which can cause duplicate quadruplets in result.

3. Final Answer:

   Missing checks to skip duplicate elements for i, j, left, and right -> Option D

4. Quick Check:

   Duplicate skipping missing = Missing checks to skip duplicate elements for i, j, left, and right [OK]

Hint: Always skip duplicates after adding quadruplet to avoid repeats [OK]

Common Mistakes:

• Not skipping duplicates causing repeated quadruplets
• Changing pointers incorrectly inside loops
• Incorrect loop boundaries causing index errors

5. Given the array nums = {2, 2, 2, 2, 2} and target 8, what is the correct output of the Four Sum problem solution that finds all unique quadruplets?

hard

A. [[2, 2, 2, 2]]

B. [[2, 2, 2, 2], [2, 2, 2, 2]]

C. []

D. [[2, 2, 2]]

Solution

1. Step 1: Check if quadruplets sum to target

   All elements are 2, so quadruplet [2, 2, 2, 2] sums to 8.

2. Step 2: Ensure uniqueness of quadruplets

   Even though elements repeat, only one unique quadruplet exists. Duplicates must be avoided.

3. Final Answer:

   [[2, 2, 2, 2]] -> Option A

4. Quick Check:

   Unique quadruplet summing to 8 = [[2, 2, 2, 2]] [OK]

Hint: Same numbers can form one unique quadruplet if sum matches target [OK]

Common Mistakes:

• Returning duplicate quadruplets multiple times
• Returning empty list when quadruplet exists
• Confusing triple with quadruplet