Three Sum Problem All Unique Triplets in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Three Sum Problem?

To find all unique triplets in an array that add up to zero.

beginner

Why do we sort the array before solving the Three Sum Problem?

Sorting helps to avoid duplicates easily and allows using two pointers to find pairs efficiently.

intermediate

Explain the two-pointer technique used in the Three Sum Problem.

After fixing one number, use two pointers starting from the next element and the end of the array to find pairs that sum to the negative of the fixed number.

intermediate

How do we ensure that the triplets are unique in the Three Sum Problem?

By skipping duplicate elements for the fixed number and also skipping duplicates when moving the two pointers.

intermediate

What is the time complexity of the common Three Sum solution using sorting and two pointers?

O(n^2), where n is the number of elements in the array.

What is the first step in solving the Three Sum Problem?

A Reverse the array

B Use a hash map

C Sort the array

D Find the maximum element

Sorting the array helps to efficiently find pairs and avoid duplicates.

After fixing one element, what technique is commonly used to find the other two elements?

A Two pointers

B Brute force

C Recursion

D Binary search

Two pointers are used to find pairs that sum to the negative of the fixed element.

How do we avoid duplicate triplets in the result?

A By using a hash set only

B By sorting and skipping duplicates

C By reversing the array

D By ignoring negative numbers

Sorting allows skipping duplicates easily to ensure unique triplets.

What is the target sum for the two pointers after fixing one element 'x'?

A Sum of all elements

B 0

C x

D -x

The two pointers look for pairs that sum to '-x' so that total sum is zero.

What is the overall time complexity of the Three Sum solution using sorting and two pointers?

A O(n^2)

B O(n)

C O(n log n)

D O(n^3)

Sorting takes O(n log n), and the two-pointer search inside a loop takes O(n^2) total.

Describe the step-by-step approach to solve the Three Sum Problem to find all unique triplets.

Think about sorting, fixing one number, and two pointers moving inward.

Explain how skipping duplicates works in the Three Sum Problem to avoid repeated triplets.

Duplicates appear when consecutive elements are equal after sorting.

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