Three Sum Problem All Unique Triplets in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Three Sum Unique Triplets Algorithm

What is the output of the following Java code that finds all unique triplets in an array which sum to zero?

DSA Java

import java.util.*;
public class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], 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 < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> result = threeSum(nums);
        System.out.println(result);
    }
}

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

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

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

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

💡 Hint

Remember the algorithm sorts the array and skips duplicates to find unique triplets summing to zero.

The code sorts the array and uses two pointers to find pairs that sum with nums[i] to zero. It skips duplicates to avoid repeated triplets. The unique triplets are [-1, -1, 2] and [-1, 0, 1].

🧠 Conceptual

intermediate

Understanding Duplicate Skipping in Three Sum

Why does the algorithm skip elements when nums[i] == nums[i - 1] during iteration?

A To ensure the array remains sorted after each iteration.

B To improve performance by skipping all negative numbers.

C To avoid counting the same triplet multiple times by skipping duplicate starting elements.

D To skip elements that cannot form any triplet.

💡 Hint

Think about how duplicates affect the uniqueness of triplets.

Skipping when nums[i] == nums[i - 1] prevents generating duplicate triplets starting with the same number, ensuring all triplets in the result are unique.

🔧 Debug

advanced

Identify the Error in Modified Three Sum Code

What error will this modified code produce when run?

DSA Java

import java.util.*;
public class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> result = threeSum(nums);
        System.out.println(result);
    }
}

A The output contains duplicate triplets because duplicates are not skipped.

B The code throws a NullPointerException at runtime.

C The code produces an empty list because the sorting is missing.

D The code causes an ArrayIndexOutOfBoundsException.

💡 Hint

Check what happens if duplicates are not skipped in the loop.

The modified code does not skip duplicates for nums[i], left, or right pointers, so duplicate triplets appear in the output.

❓ Predict Output

advanced

Output of Three Sum with All Positive Numbers

What is the output of the threeSum method when the input array contains only positive numbers?

DSA Java

import java.util.*;
public class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], 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 < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        List<List<Integer>> result = threeSum(nums);
        System.out.println(result);
    }
}

A [[1, 2, -3]]

B [[2, 3, -5]]

C [[1, 1, -2]]

D []

💡 Hint

Sum of three positive numbers cannot be zero.

Since all numbers are positive, no three numbers can sum to zero, so the result is an empty list.

🚀 Application

expert

Number of Unique Triplets Summing to Zero

Given the input array [-2, 0, 1, 1, 2, -1, -1], how many unique triplets sum to zero?

A 5

B 4

C 2

D 3

💡 Hint

Find all unique triplets without duplicates that sum to zero.

The unique triplets are [-2, 0, 2], [-2, 1, 1], [-1, -1, 2], and [-1, 0, 1], totaling 4.

Practice

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

easy

A. Sort the array in ascending order

B. Find the maximum sum of any three elements

C. Find all unique triplets in an array that sum to zero

D. Count the number of pairs that sum to zero

Solution

1. Step 1: Understand the problem statement

   The Three Sum Problem asks to find all unique sets of three numbers in an array whose sum is zero.

2. Step 2: Identify the goal

   The goal is to find triplets (three numbers) that add up exactly to zero without duplicates.

3. Final Answer:

   Find all unique triplets in an array that sum to zero -> Option C

4. Quick Check:

   Three Sum Problem = Find triplets summing to zero [OK]

Hint: Look for three numbers adding to zero without repeats [OK]

Common Mistakes:

• Thinking it finds pairs instead of triplets
• Assuming it sorts the array only
• Looking for maximum sum instead of zero sum

2. Which of the following Java code snippets correctly initializes an array to be used for solving the Three Sum Problem?

easy

A. int[] nums = (-1, 0, 1, 2, -1, -4);

B. int nums = {-1, 0, 1, 2, -1, -4};

C. int nums[] = new int(-1, 0, 1, 2, -1, -4);

D. int[] nums = new int[]{-1, 0, 1, 2, -1, -4};

Solution

1. Step 1: Check Java array initialization syntax

   In Java, arrays are initialized with new int[]{...} or directly with curly braces during declaration.

2. Step 2: Validate each option

   int[] nums = new int[]{-1, 0, 1, 2, -1, -4}; uses correct syntax: int[] nums = new int[]{-1, 0, 1, 2, -1, -4};. Others have syntax errors.

3. Final Answer:

   int[] nums = new int[]{-1, 0, 1, 2, -1, -4}; -> Option D

4. Quick Check:

   Correct Java array syntax = int[] nums = new int[]{-1, 0, 1, 2, -1, -4}; [OK]

Hint: Use new int[]{...} to initialize arrays in Java [OK]

Common Mistakes:

• Using parentheses instead of braces
• Missing 'new' keyword
• Declaring array without type

3. What will be the output of the following Java code snippet that attempts to find unique triplets summing to zero?

import java.util.*;
public class ThreeSum {
  public static List threeSum(int[] nums) {
    List res = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
      if (i > 0 && nums[i] == nums[i - 1]) continue;
      int left = i + 1, right = nums.length - 1;
      while (left < right) {
        int sum = nums[i] + nums[left] + nums[right];
        if (sum == 0) {
          res.add(Arrays.asList(nums[i], 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 < 0) left++;
        else right--;
      }
    }
    return res;
  }
  public static void main(String[] args) {
    int[] nums = {-1, 0, 1, 2, -1, -4};
    System.out.println(threeSum(nums));
  }
}

medium

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

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

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

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

Solution

1. Step 1: Sort and iterate through the array

   The array after sorting is [-4, -1, -1, 0, 1, 2]. The code skips duplicates and uses two pointers to find triplets summing to zero.

2. Step 2: Identify unique triplets summing to zero

   Triplets found are [-1, -1, 2] and [-1, 0, 1]. These are added to the result list.

3. Final Answer:

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

4. Quick Check:

   Unique triplets summing zero = [[-1, -1, 2], [-1, 0, 1]] [OK]

Hint: Sort array, use two pointers to find zero sum triplets [OK]

Common Mistakes:

• Not sorting array before two-pointer approach
• Including duplicate triplets
• Incorrect pointer movement causing wrong sums

4. Identify the bug in the following Java code snippet for the Three Sum Problem and select the correct fix:

public List threeSum(int[] nums) {
  List res = new ArrayList<>();
  Arrays.sort(nums);
  for (int i = 0; i < nums.length - 2; i++) {
    if (nums[i] == nums[i + 1]) continue;
    int left = i + 1, right = nums.length - 1;
    while (left < right) {
      int sum = nums[i] + nums[left] + nums[right];
      if (sum == 0) {
        res.add(Arrays.asList(nums[i], nums[left], nums[right]));
        left++;
        right--;
      } else if (sum < 0) left++;
      else right--;
    }
  }
  return res;
}

medium

A. Remove the sorting step Arrays.sort(nums);

B. Change if (nums[i] == nums[i + 1]) continue; to if (i > 0 && nums[i] == nums[i - 1]) continue;

C. Change while (left < right) to while (left <= right)

D. Add left++ and right-- after the while loop

Solution

1. Step 1: Identify the duplicate skipping condition

   The code incorrectly checks nums[i] == nums[i + 1] which can cause index out of bounds and wrong duplicate skipping.

2. Step 2: Correct duplicate skipping logic

   The correct check is if (i > 0 && nums[i] == nums[i - 1]) continue; to skip duplicates properly without errors.

3. Final Answer:

   Change if (nums[i] == nums[i + 1]) continue; to if (i > 0 && nums[i] == nums[i - 1]) continue; -> Option B

4. Quick Check:

   Proper duplicate skip check = Change if (nums[i] == nums[i + 1]) continue; to if (i > 0 && nums[i] == nums[i - 1]) continue; [OK]

Hint: Skip duplicates by comparing current with previous element [OK]

Common Mistakes:

• Checking next element instead of previous for duplicates
• Not sorting array before duplicate check
• Incorrect pointer conditions causing infinite loops

5. Given an array nums = [0, 0, 0, 0], what is the correct output of the Three Sum Problem algorithm that finds all unique triplets summing to zero?

hard

A. [[0, 0, 0]]

B. [[0, 0, 0], [0, 0, 0]]

C. []

D. [[0, 0]]

Solution

1. Step 1: Understand the input array with duplicates

   The array has four zeros. The algorithm must find unique triplets summing to zero.

2. Step 2: Identify unique triplets

   Only one unique triplet exists: [0, 0, 0]. Duplicates are skipped to avoid repeated triplets.

3. Final Answer:

   [[0, 0, 0]] -> Option A

4. Quick Check:

   Unique zero triplet = [[0, 0, 0]] [OK]

Hint: One triplet of zeros regardless of duplicates [OK]

Common Mistakes:

• Returning multiple identical triplets
• Returning empty list thinking no sum possible
• Returning pairs instead of triplets