Four Sum Problem All Unique Quadruplets in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Four Sum with Small Array

What is the output of the following Java code that finds all unique quadruplets summing to target 0?

DSA Java

import java.util.*;
public class FourSum {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> 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;
            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) {
                    int sum = 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;
    }
    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        List<List<Integer>> result = fourSum(nums, 0);
        System.out.println(result);
    }
}

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

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

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

D [[-1, -1, 1, 1], [0, 0, 0, 0]]

💡 Hint

Think about sorting and skipping duplicates to get unique quadruplets.

The code sorts the array and uses two nested loops with two pointers to find quadruplets summing to zero. It skips duplicates to ensure uniqueness. The correct quadruplets are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1].

🧠 Conceptual

intermediate

Understanding Duplicate Skipping in Four Sum

Why does the Four Sum solution skip elements when nums[i] == nums[i - 1] or nums[j] == nums[j - 1]?

A To avoid counting the same quadruplet multiple times by skipping duplicate elements.

B To speed up the algorithm by skipping unnecessary elements.

C To handle negative numbers correctly in the sum calculation.

D To ensure the array remains sorted after processing.

💡 Hint

Think about how duplicates affect the uniqueness of quadruplets.

Skipping duplicates prevents adding the same quadruplet more than once, ensuring the result contains only unique quadruplets.

🔧 Debug

advanced

Identify the Error in Four Sum Implementation

What error will the following code produce when run?

DSA Java

import java.util.*;
public class FourSumBug {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> 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;
            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) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[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--;
                    }
                }
            }
        }
        return res;
    }
}

A Infinite loop because left and right pointers are not updated

B NullPointerException because res is not initialized

C No error, code runs correctly

D ArrayIndexOutOfBoundsException due to incorrect loop boundary in outer loop

💡 Hint

Check the loop conditions carefully for array boundaries.

The outer loop runs with i <= n - 3, which allows i to be n-3, but inside the inner loops and pointers, this causes index out of bounds when accessing nums[j] or pointers.

🚀 Application

advanced

Number of Unique Quadruplets for Large Input

Given the array nums = [2, 2, 2, 2, 2] and target = 8, how many unique quadruplets does the Four Sum algorithm find?

A 0

B 1

C 5

D 10

💡 Hint

Consider how duplicates are handled and the quadruplet sums.

All elements are 2, so the only quadruplet summing to 8 is [2, 2, 2, 2]. The algorithm returns only one unique quadruplet.

❓ Predict Output

expert

Output of Four Sum with Negative and Positive Numbers

What is the output of this Java code snippet that finds all unique quadruplets summing to 2?

DSA Java

import java.util.*;
public class FourSumExpert {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> 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;
            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) {
                    int sum = 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;
    }
    public static void main(String[] args) {
        int[] nums = {-3, -1, 0, 2, 4, 5};
        List<List<Integer>> result = fourSum(nums, 2);
        System.out.println(result);
    }
}

A [[-3, -1, 2, 4]]

B [[-3, 0, 2, 3], [-1, 0, 2, 1]]

C [[-3, -1, 0, 6]]

D []

💡 Hint

Check sums carefully and remember the array is sorted.

Only the quadruplet [-3, -1, 2, 4] sums to 2. Other options contain numbers not in the array or sums that don't match.

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