Four Sum Problem All Unique Quadruplets in DSA Java - Deep Dive

Overview - Four Sum Problem All Unique Quadruplets

What is it?

The Four Sum Problem asks us to find all unique groups of four numbers in a list that add up to a specific target number. Each group of four numbers is called a quadruplet. We want to list all such quadruplets without repeating any. This problem helps us practice combining searching and sorting techniques.

Why it matters

Without a method to find these quadruplets efficiently, checking every possible group would take too long, especially with large lists. This problem teaches us how to reduce unnecessary work and avoid duplicates, which is important in many real-world tasks like data analysis and finding patterns. Without it, programs would be slow and less useful.

Where it fits

Before this, you should understand arrays, sorting, and the two-pointer technique. After mastering this, you can learn more complex problems like k-sum or advanced backtracking. This problem builds a bridge between simple searching and more complex combination problems.

Mental Model

Core Idea

Find all unique sets of four numbers that sum to the target by sorting the list and using nested loops with two pointers to efficiently explore combinations without duplicates.

Think of it like...

Imagine you have a group of friends and want to find all unique teams of four whose combined ages add up to a birthday milestone. You first sort them by age, then pick pairs and look for matching pairs that complete the team without repeating the same group.

Sorted array: [a1, a2, a3, ..., an]

Outer loop i -> a1 to an-3
  Inner loop j -> i+1 to an-2
    Two pointers: left = j+1, right = n-1
      Move left and right to find sums equal to target

Result: unique quadruplets collected

Build-Up - 7 Steps

1

Foundation

Understanding the problem and input

Concept: Learn what the problem asks and the input format.

We have an array of integers and a target sum. We want to find all unique quadruplets (four numbers) that add up exactly to the target. The output is a list of these quadruplets, with no repeats.

Result

Clear problem statement and input/output understanding.

Understanding the problem fully is key before trying to solve it, preventing wasted effort on wrong approaches.

2

Foundation

Sorting the array for easier searching

Concept: Sort the array to help find quadruplets efficiently and avoid duplicates.

Sorting arranges numbers from smallest to largest. This helps us use two pointers to find pairs quickly and skip duplicates by comparing neighbors.

Result

Sorted array ready for efficient searching.

Sorting transforms a complex search into a structured process, enabling faster and cleaner solutions.

3

Intermediate

Using nested loops to fix first two numbers

🤔Before reading on: Do you think fixing two numbers first reduces the problem complexity or not? Commit to your answer.

Concept: Fix two numbers with loops, then find the other two with two pointers.

We use two loops: outer loop picks the first number, inner loop picks the second. For each pair, we look for two more numbers that complete the quadruplet. This breaks the problem into smaller parts.

Result

Reduced problem to finding pairs that sum to (target - first two numbers).

Breaking the problem into smaller parts simplifies searching and helps manage complexity.

4

Intermediate

Applying two-pointer technique for last two numbers

🤔Before reading on: Will moving pointers inward always find all pairs or can some be missed? Commit to your answer.

Concept: Use two pointers moving from both ends to find pairs summing to the needed value.

Set left pointer after second fixed number and right pointer at the end. Move pointers inward based on sum compared to needed value. If sum too small, move left up; if too big, move right down.

Result

Efficiently find pairs without checking every combination.

Two pointers exploit sorted order to find pairs in linear time, greatly improving efficiency.

5

Intermediate

Skipping duplicates to ensure unique quadruplets

🤔Before reading on: Do you think skipping duplicates is necessary or can duplicates be filtered after collecting results? Commit to your answer.

Concept: Skip repeated numbers during loops and pointer moves to avoid duplicate quadruplets.

After sorting, if the current number is same as previous, skip it. Similarly, after finding a quadruplet, move pointers past duplicates. This prevents repeated groups in output.

Result

Output contains only unique quadruplets.

Handling duplicates during search avoids extra work and ensures clean results.

6

Advanced

Implementing complete Java solution with comments

🤔Before reading on: Predict the output quadruplets for input [1,0,-1,0,-2,2] and target 0. Commit to your answer.

Concept: Write full Java code combining sorting, loops, two pointers, and duplicate skipping.

public List> fourSum(int[] nums, int target) { List> res = new ArrayList<>(); Arrays.sort(nums); int n = nums.length; for (int i = 0; i < n - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates for (int j = i + 1; j < n - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; // skip duplicates int left = j + 1, right = n - 1; while (left < right) { long sum = (long)nums[i] + nums[j] + nums[left] + nums[right]; if (sum == target) { res.add(Arrays.asList(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 res; }

Result

For input [1,0,-1,0,-2,2] and target 0, output is [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Seeing the full code connects all concepts and shows how they work together in practice.

7

Expert

Handling integer overflow and optimization tricks

🤔Before reading on: Do you think adding four integers can cause overflow in Java? Commit to your answer.

Concept: Use long type for sum to avoid overflow; add early breaks to skip impossible sums.

In Java, adding four ints can overflow if values are large. Casting to long before addition prevents wrong sums. Also, if smallest possible sum is greater than target, break early; if largest possible sum is smaller, continue to next iteration. These optimizations save time.

Result

Robust and faster code that handles edge cases and large inputs.

Understanding language limits and adding early checks prevents bugs and improves performance in real systems.

Under the Hood

The algorithm first sorts the array to arrange numbers in order. Then it uses two nested loops to fix the first two numbers. For the remaining two numbers, it uses two pointers starting from both ends of the remaining array segment. By moving pointers inward based on the sum comparison, it finds pairs efficiently. Duplicate skipping is done by comparing current values with previous ones to avoid repeated quadruplets. The sorting and two-pointer approach reduce the time complexity from exponential to roughly O(n^3).

Why designed this way?

Brute force checking all quadruplets would be O(n^4), too slow for large inputs. Sorting enables the two-pointer technique, which is a classic method to find pairs in O(n). Fixing two numbers and searching for pairs combines these ideas to reduce complexity. Skipping duplicates during search avoids extra memory and post-processing. This design balances speed, simplicity, and correctness.

Input array
  ↓ sort
Sorted array: [a1, a2, ..., an]

Outer loop i (0 to n-4)
  ↓
Inner loop j (i+1 to n-3)
  ↓
Two pointers left = j+1, right = n-1
  ↔ move pointers inward based on sum

Collect quadruplets when sum == target

Skip duplicates at i, j, left, right

Output: unique quadruplets

Myth Busters - 4 Common Misconceptions

Quick: Does sorting the array change the quadruplets found? Commit yes or no.

Common Belief: Sorting the array changes the quadruplets and their order, so it might miss some combinations.

Reality: Sorting only rearranges numbers but does not remove or change any quadruplets. It helps find all quadruplets efficiently without missing any.

Why it matters: Believing sorting loses quadruplets might prevent learners from using the most efficient approach, leading to slow or incorrect solutions.

Quick: Can we find quadruplets by just checking pairs without sorting? Commit yes or no.

Common Belief: We can find quadruplets by checking all pairs without sorting, and it will be efficient enough.

Reality: Without sorting, checking all quadruplets is O(n^4), which is too slow for large inputs. Sorting enables two-pointer technique to reduce complexity to O(n^3).

Why it matters: Ignoring sorting leads to inefficient code that won't scale, causing performance issues in real applications.

Quick: Is it okay to add quadruplets to the result list without checking duplicates? Commit yes or no.

Common Belief: We can add all found quadruplets directly; duplicates can be removed later if needed.

Reality: Adding duplicates wastes memory and time. Skipping duplicates during search is more efficient and cleaner.

Why it matters: Not handling duplicates early leads to bloated results and extra processing, making code slower and harder to maintain.

Quick: Does integer overflow never happen when adding four integers in Java? Commit yes or no.

Common Belief: Integer overflow is not a concern when adding four integers because inputs are usually small.

Reality: Integer overflow can happen if numbers are large, causing wrong sums and incorrect results. Using long type prevents this.

Why it matters: Ignoring overflow can cause subtle bugs that are hard to detect and fix in production.

Expert Zone

1

Using long for sum calculation is critical in languages like Java to avoid overflow, even if inputs seem small.

2

Early termination checks based on minimum and maximum possible sums can drastically reduce runtime on sorted arrays.

3

Skipping duplicates must be done carefully at all four positions (i, j, left, right) to ensure no repeated quadruplets.

When NOT to use

This approach is not suitable if the input array is unsorted and cannot be sorted due to constraints, or if the problem requires counting quadruplets with duplicates allowed. In such cases, hash-based methods or backtracking might be better.

Production Patterns

In real systems, this pattern is used in financial data analysis to find combinations of transactions matching a target sum, or in recommendation engines to find groups of items meeting criteria. Optimizations like early breaks and overflow checks are standard in production code.

Connections

Two Sum Problem

Builds-on

Understanding the simpler two sum problem helps grasp how fixing two numbers and searching pairs with two pointers extends to four sum.

Combination Sum Problems

Same pattern

Four sum is a specific case of combination sum problems where we look for fixed-size subsets adding to a target, teaching general subset search techniques.

Financial Portfolio Balancing

Application

Finding quadruplets that sum to a target is similar to selecting four investments that meet a total budget, showing how algorithms solve real-world allocation problems.

Common Pitfalls

#1 Not skipping duplicates leads to repeated quadruplets in output.

Wrong approach:

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

Correct approach:

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, right = n - 1;
while (left < right) {
if (sum == target) {
res.add(Arrays.asList(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--;
}
}
}
}

Root cause:

Not understanding the importance of skipping duplicates during iteration and pointer movement.

#2 Adding integers directly without checking overflow causes wrong sums.

Wrong approach:

int sum = nums[i] + nums[j] + nums[left] + nums[right];

Correct approach:

long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];

Root cause:

Ignoring integer overflow possibility in sum calculation.

#3 Not sorting the array before searching leads to incorrect two-pointer behavior.

Wrong approach:

Use two pointers on unsorted array without sorting first.

Correct approach:

Arrays.sort(nums); // sort before two-pointer search

Root cause:

Misunderstanding that two-pointer technique requires sorted input.

Key Takeaways

Sorting the array is essential to efficiently find quadruplets and avoid duplicates.

Fixing two numbers and using two pointers for the remaining two reduces complexity from O(n^4) to O(n^3).

Skipping duplicates during iteration and pointer movement ensures unique quadruplets without extra memory.

Using long type for sum calculation prevents integer overflow bugs in Java.

Early termination checks based on possible sums optimize performance on large inputs.

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