Three Sum Problem All Unique Triplets in DSA Java

Mental Model

Find three numbers in a list that add up to zero without repeating any triplet.

Analogy: Imagine you have a group of friends with different ages, and you want to find three friends whose ages add up exactly to zero, but you don't want to count the same group twice.

nums: [-4] -> [-1] -> [-1] -> [0] -> [1] -> [2] -> null
indexes:  0       1       2       3      4      5

Dry Run Walkthrough

Input: nums = [-1, 0, 1, 2, -1, -4]

Goal: Find all unique triplets that sum to zero

Step 1: Sort the array to get [-4, -1, -1, 0, 1, 2]

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

Why: Sorting helps to use two pointers and avoid duplicates easily

Step 2: Set i=0 (value -4), set left=1, right=5

i=-4, left=-1, right=2

Why: Start with first element and two pointers to find pairs that sum with i to zero

Step 3: Calculate sum = -4 + (-1) + 2 = -3 < 0, move left to 2

i=-4, left=-1 (index 2), right=2

Why: Sum less than zero means we need a bigger number, move left pointer right

Step 4: Calculate sum = -4 + (-1) + 2 = -3 < 0, move left to 3

i=-4, left=0, right=2

Why: Still less than zero, move left pointer right

Step 5: Calculate sum = -4 + 0 + 2 = -2 < 0, move left to 4

i=-4, left=1, right=2

Why: Sum less than zero, move left pointer right

Step 6: Calculate sum = -4 + 1 + 2 = -1 < 0, move left to 5

i=-4, left=2, right=2

Why: Sum less than zero, move left pointer right but now left == right, stop

Step 7: Increment i to 1 (value -1), set left=2, right=5

i=-1, left=-1, right=2

Why: Move to next element to find new triplets

Step 8: Calculate sum = -1 + (-1) + 2 = 0, found triplet [-1, -1, 2], move left and right skipping duplicates

triplets = [[-1, -1, 2]]

Why: Sum zero means valid triplet, move pointers to find others

Step 9: left moves to 3 (0), right moves to 4 (1)

i=-1, left=0, right=1

Why: Continue searching for other pairs with i

Step 10: Calculate sum = -1 + 0 + 1 = 0, found triplet [-1, 0, 1], move left and right skipping duplicates

triplets = [[-1, -1, 2], [-1, 0, 1]]

Why: Found another valid triplet

Step 11: left moves to 4, right moves to 3, pointers cross, increment i to 2

i=-1 (index 2), left=3, right=4

Why: No more pairs for this i, move to next i

Step 12: Skip i=2 because nums[2] == nums[1] to avoid duplicates

i=3 (value 0)

Why: Avoid duplicate triplets by skipping same values for i

Step 13: Set left=4 (1), right=5 (2), calculate sum = 0 + 1 + 2 = 3 > 0, move right left

i=0, left=1, right=2

Why: Sum too big, move right pointer left to reduce sum

Step 14: right moves to 4, left == right, stop

No new triplets

Why: Pointers crossed, no more pairs for i=3

Result:

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

Annotated Code

DSA Java

import java.util.*;

public class ThreeSum {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // sort array to use two pointers
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates for i
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], 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 < 0) {
                    left++; // need bigger sum
                } else {
                    right--; // need smaller sum
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> triplets = threeSum(nums);
        for (List<Integer> triplet : triplets) {
            System.out.println(triplet.get(0) + " -> " + triplet.get(1) + " -> " + triplet.get(2) + " -> null");
        }
    }
}

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

sort array to enable two-pointer technique and duplicate skipping

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

skip duplicate values for i to avoid repeated triplets

while (left < right) {

iterate with two pointers to find pairs that sum with nums[i] to zero

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

calculate current triplet sum

if (sum == 0) {

found a valid triplet

left++; right--;

move both pointers inward to find new pairs

while (left < right && nums[left] == nums[left - 1]) left++; // skip duplicates

skip duplicate values for left pointer

while (left < right && nums[right] == nums[right + 1]) right--; // skip duplicates

skip duplicate values for right pointer

else if (sum < 0) { left++; }

sum too small, move left pointer right to increase sum

else { right--; }

sum too big, move right pointer left to decrease sum

Output

-1 -> -1 -> 2 -> null

-1 -> 0 -> 1 -> null

Complexity Analysis

Time: O(n^2) because we sort once O(n log n) and then use two nested loops with two pointers for O(n^2)

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

vs Alternative: Naive approach is O(n^3) by checking all triplets; this two-pointer method is much faster

Edge Cases

empty array

returns empty list, no triplets found

DSA Java

for (int i = 0; i < nums.length - 2; i++) {

array with less than 3 elements

returns empty list, no triplets possible

DSA Java

for (int i = 0; i < nums.length - 2; i++) {

array with all zeros

returns one triplet [0, 0, 0] only once

DSA Java

while (left < right && nums[left] == nums[left - 1]) left++;

array with duplicates

skips duplicate triplets by checking duplicates for i, left, and right

DSA Java

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

When to Use This Pattern

When asked to find triplets that sum to zero or a target with unique results, use sorting plus two pointers to efficiently find all unique triplets.

Common Mistakes

Mistake: Not sorting the array before two-pointer approach
Fix: Sort the array first to enable two-pointer technique and duplicate skipping

Mistake: Not skipping duplicates for i, left, or right pointers
Fix: Add checks to skip duplicate values to avoid repeated triplets

Mistake: Moving pointers incorrectly after finding a triplet
Fix: Move both left and right pointers inward and skip duplicates before continuing

Summary

Finds all unique triplets in an array that sum to zero.

Use when you need to find combinations of three numbers adding to zero without duplicates.

Sort the array and use two pointers to efficiently find triplets and skip duplicates.

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