Three Sum Problem All Unique Triplets in DSA Java - Deep Dive

Overview - Three Sum Problem All Unique Triplets

What is it?

The Three Sum Problem asks us to find all unique groups of three numbers in a list that add up to zero. Each group is called a triplet, and no two triplets should have the same numbers. This problem helps us understand how to efficiently search and combine elements in a list to meet a condition.

Why it matters

Without a method like this, finding all such triplets would take a very long time, especially for big lists. This problem teaches us how to reduce unnecessary checks and avoid duplicates, which is important in many real-world tasks like finding combinations or patterns in data. Without it, programs would be slower and less efficient.

Where it fits

Before this, you should know about arrays, sorting, and basic loops. After this, you can learn about more complex combination problems, two-pointer techniques, and hashing for faster searches.

Mental Model

Core Idea

Find three numbers that sum to zero by sorting the list and using two pointers to efficiently find pairs that complement each chosen number.

Think of it like...

Imagine you have a group of friends with different heights, and you want to find three friends whose heights add up to exactly zero when you consider some as positive and some as negative. Sorting them by height helps you quickly find the right trio without checking every possible group.

Sorted Array: [-4, -1, -1, 0, 1, 2]
Choose first number (i) -> Fix it
Use two pointers (left, right) to find pairs:

  i
  ↓
[-4, -1, -1, 0, 1, 2]
     ↑           ↑
   left        right

Move left and right pointers inward based on sum:
If sum < 0 -> move left right
If sum > 0 -> move right left
If sum == 0 -> record triplet and move both pointers

Repeat for each i

Build-Up - 6 Steps

1

Foundation

Understanding the Problem Statement

Concept: Learn what the problem asks: find all unique triplets that sum to zero.

Given an array of integers, we want to find all sets of three numbers where the sum is zero. For example, in [-1, 0, 1, 2, -1, -4], the triplets are [-1, -1, 2] and [-1, 0, 1]. We must avoid duplicates.

Result

Clear understanding of the goal: find unique triplets summing to zero.

Understanding the exact problem prevents confusion and sets the stage for choosing the right approach.

2

Foundation

Brute Force Approach and Its Limits

Concept: Try all possible triplets and check their sums.

Check every combination of three numbers using three nested loops. For each triplet, check if the sum is zero. Store unique triplets to avoid duplicates. Example code snippet: for i in 0 to n-3: for j in i+1 to n-2: for k in j+1 to n-1: if nums[i] + nums[j] + nums[k] == 0: add triplet if unique This approach takes O(n^3) time.

Result

All triplets found but very slowly for large arrays.

Knowing brute force helps appreciate why we need faster methods.

3

Intermediate

Sorting and Two-Pointer Technique

🤔Before reading on: do you think sorting the array helps find triplets faster or slower? Commit to your answer.

Concept: Sort the array to use two pointers for finding pairs that sum to a target.

Sort the array first. Then, for each number, use two pointers starting just after it and at the end of the array. Move pointers inward based on the sum compared to the target (-nums[i]). This reduces time to O(n^2). Example: nums = [-4, -1, -1, 0, 1, 2] For i=0 (-4), target=4 left=1, right=5 sum = nums[left] + nums[right] Adjust pointers until sum == target or pointers cross.

Result

Faster search for pairs that complement the chosen number.

Sorting enables a structured search that skips many unnecessary checks.

4

Intermediate

Avoiding Duplicate Triplets

🤔Before reading on: do you think skipping duplicates is necessary for correctness or just for cleaner output? Commit to your answer.

Concept: Skip repeated numbers to avoid duplicate triplets in the result.

After sorting, duplicates appear next to each other. When choosing the first number or moving pointers, skip numbers equal to the previous one. This prevents adding the same triplet multiple times. Example: If nums[i] == nums[i-1], continue to next i. Similarly, after finding a triplet, move left and right pointers past duplicates.

Result

Unique triplets only, no repeats in output.

Skipping duplicates is essential to meet problem requirements and avoid redundant work.

5

Advanced

Complete Java Implementation with Comments

🤔Before reading on: do you think the two-pointer approach can handle negative and positive numbers together correctly? Commit to your answer.

Concept: Putting all pieces together in runnable Java code.

public List> threeSum(int[] nums) { List> result = new ArrayList<>(); Arrays.sort(nums); // Sort array for (int i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates int left = i + 1; int 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])); while (left < right && nums[left] == nums[left + 1]) left++; // Skip duplicates while (left < right && nums[right] == nums[right - 1]) right--; // Skip duplicates left++; right--; } else if (sum < 0) { left++; } else { right--; } } } return result; }

Result

Correct, efficient Java code that finds all unique triplets summing to zero.

Seeing the full code clarifies how sorting, two pointers, and duplicate skipping work together.

6

Expert

Performance and Edge Case Considerations

🤔Before reading on: do you think the algorithm handles empty arrays or arrays with fewer than three elements gracefully? Commit to your answer.

Concept: Understand how the algorithm behaves with special inputs and its time complexity.

The algorithm runs in O(n^2) time, which is efficient for this problem. It handles empty or small arrays by simply returning an empty list since the loop conditions fail. Edge cases like all zeros or all positives are handled naturally by the sorting and pointer logic. Example edge case: nums = [0, 0, 0, 0] Output: [[0, 0, 0]] The algorithm skips duplicates to avoid repeated triplets.

Result

Robust solution that works correctly and efficiently across inputs.

Knowing edge cases and performance helps write reliable code and avoid bugs in production.

Under the Hood

The algorithm first sorts the array to arrange numbers in order. Then it picks each number as a fixed first element. For each fixed element, it uses two pointers starting from the next element and the end of the array to find pairs that sum to the negative of the fixed element. Moving pointers inward adjusts the sum efficiently without checking all pairs. Skipping duplicates prevents repeated triplets. This reduces the problem from O(n^3) to O(n^2) time.

Why designed this way?

Sorting allows the two-pointer technique to work because the array is ordered, making it easy to decide which pointer to move based on the sum. The design balances simplicity and efficiency. Alternatives like hash sets exist but may use more memory or be less straightforward. The two-pointer approach is a classic pattern for sum problems in sorted arrays.

Input Array
  ↓
Sorted Array
  ↓
For each i (fixed number):
  ┌─────────────────────────────┐
  │ Two pointers: left and right │
  │ Move pointers based on sum   │
  │ Skip duplicates              │
  └─────────────────────────────┘
  ↓
Collect unique triplets
  ↓
Return result

Myth Busters - 4 Common Misconceptions

Quick: Do you think sorting the array changes the original problem's answer? Commit yes or no.

Common Belief: Sorting the array might change the triplets found or miss some solutions.

Reality: Sorting does not change the set of triplets that sum to zero; it only rearranges elements to make searching efficient.

Why it matters: Believing sorting changes answers might prevent learners from using the most efficient approach.

Quick: Do you think the two-pointer method works without sorting? Commit yes or no.

Common Belief: Two-pointer technique can be applied directly on unsorted arrays.

Reality: Two-pointer requires a sorted array to decide pointer movement based on sum comparisons.

Why it matters: Trying two-pointer on unsorted arrays leads to incorrect results and wasted effort.

Quick: Do you think skipping duplicates is optional if you just want all triplets? Commit yes or no.

Common Belief: Skipping duplicates is just for cleaner output, not necessary for correctness.

Reality: Skipping duplicates is necessary to meet the problem requirement of unique triplets; otherwise, duplicates appear.

Why it matters: Ignoring duplicates leads to wrong answers and fails problem constraints.

Quick: Do you think the algorithm can find triplets with any sum target other than zero without changes? Commit yes or no.

Common Belief: The same algorithm works for any target sum without modification.

Reality: The algorithm can be adapted for other targets by changing the target sum calculation, but the core logic remains similar.

Why it matters: Understanding this helps generalize the approach to other problems.

Expert Zone

1

The order of skipping duplicates is crucial: skipping duplicates for the fixed element and for the left and right pointers must be done carefully to avoid missing valid triplets or adding duplicates.

2

The two-pointer approach relies on the array being sorted once; re-sorting inside loops would ruin performance.

3

Handling integer overflow is rarely discussed but important in languages like Java when summing large integers; casting to long or checking bounds can prevent bugs.

When NOT to use

This approach is not suitable if the input is extremely large and memory is limited, or if the array is not easily sortable (e.g., streaming data). Alternatives include hashing-based methods or approximate algorithms for very large datasets.

Production Patterns

In real systems, this pattern is used in financial fraud detection to find suspicious triplets of transactions, in recommendation engines to find item combinations, and in coding interviews to test problem-solving and optimization skills.

Connections

Two Sum Problem

Builds-on

Understanding the simpler Two Sum problem helps grasp the two-pointer technique used in Three Sum.

Sorting Algorithms

Depends on

Efficient sorting is foundational for the two-pointer approach to work correctly and quickly.

Chemical Reaction Balancing

Analogous pattern

Balancing chemical equations involves finding combinations of elements that sum to zero net charge or mass, similar to finding triplets summing to zero.

Common Pitfalls

#1 Not sorting the array before applying two-pointer technique.

Wrong approach:

int left = i + 1;
int right = nums.length - 1;
// Without sorting
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
// add triplet
}
// move pointers without sorting logic
}

Correct approach:

Arrays.sort(nums);
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
// add triplet
}
// move pointers based on sum comparison
}

Root cause:

Misunderstanding that two-pointer requires sorted input to function correctly.

#2 Not skipping duplicates leads to repeated triplets in output.

Wrong approach:

for (int i = 0; i < nums.length - 2; i++) {
// no check for nums[i] == nums[i-1]
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
if (sum == 0) {
result.add(...);
// no skipping duplicates for left and right
left++;
right--;
}
}
}

Correct approach:

for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
if (sum == 0) {
result.add(...);
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}

Root cause:

Not realizing duplicates appear consecutively after sorting and must be skipped explicitly.

#3 Using three nested loops without optimization causes slow performance.

Wrong approach:

for (int i = 0; i < n-2; i++) {
for (int j = i+1; j < n-1; j++) {
for (int k = j+1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
// add triplet
}
}
}
}

Correct approach:

Arrays.sort(nums);
for (int i = 0; i < n-2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue;
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
// add triplet
// skip duplicates
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}

Root cause:

Not knowing the two-pointer optimization reduces time complexity from cubic to quadratic.

Key Takeaways

The Three Sum Problem finds all unique triplets in an array that sum to zero by combining sorting and the two-pointer technique.

Sorting the array is essential to efficiently move pointers and avoid unnecessary checks.

Skipping duplicates at every step ensures the output contains only unique triplets, meeting problem requirements.

The two-pointer approach reduces time complexity from O(n^3) to O(n^2), making the solution practical for larger inputs.

Understanding edge cases and performance considerations leads to robust and efficient implementations.

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