Three Sum Problem All Unique Triplets in DSA Java - Execution Trace

Concept Flow - Three Sum Problem All Unique Triplets

Sort the array

↓

For each element i

↓

Set left = i+1, right = end

↓

While left < right

↓

Sum < 0

↓

left++

↓

Sum == 0

↓

Add triplet

↓

Skip duplicates

↓

Move left and right

↓

Repeat while left < right

↓

Repeat for next i

↓

Return all unique triplets

Sort the array, then for each element use two pointers to find pairs that sum to zero with it, skipping duplicates.

Execution Sample

DSA Java

int[] nums = {-1, 0, 1, 2, -1, -4};
Arrays.sort(nums);
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) {
      // add triplet
      // skip duplicates for left and 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--;
  }
}

Sorts the array and uses two pointers to find all unique triplets that sum to zero.

Execution Table

Step	Operation	i	left	right	Sum	Action	Triplets Found	Array State
1	Sort array	-	-	-	-	-	[]	[-4, -1, -1, 0, 1, 2]
2	Set i=0	0	-	-	-	-	[]	[-4, -1, -1, 0, 1, 2]
3	Set left=1, right=5	0	1	5	-	-	[]	[-4, -1, -1, 0, 1, 2]
4	Calculate sum	0	1	5	-4 + (-1) + 2 = -3	sum < 0, left++	[]	[-4, -1, -1, 0, 1, 2]
5	Update left=2	0	2	5	-	-	[]	[-4, -1, -1, 0, 1, 2]
6	Calculate sum	0	2	5	-4 + (-1) + 2 = -3	sum < 0, left++	[]	[-4, -1, -1, 0, 1, 2]
7	Update left=3	0	3	5	-	-	[]	[-4, -1, -1, 0, 1, 2]
8	Calculate sum	0	3	5	-4 + 0 + 2 = -2	sum < 0, left++	[]	[-4, -1, -1, 0, 1, 2]
9	Update left=4	0	4	5	-	-	[]	[-4, -1, -1, 0, 1, 2]
10	Calculate sum	0	4	5	-4 + 1 + 2 = -1	sum < 0, left++	[]	[-4, -1, -1, 0, 1, 2]
11	Update left=5	0	5	5	-	-	[]	[-4, -1, -1, 0, 1, 2]
12	left >= right, move to next i	1	-	-	-	-	[]	[-4, -1, -1, 0, 1, 2]
13	Set i=1	1	-	-	-	-	[]	[-4, -1, -1, 0, 1, 2]
14	Set left=2, right=5	1	2	5	-	-	[]	[-4, -1, -1, 0, 1, 2]
15	Calculate sum	1	2	5	-1 + (-1) + 2 = 0	sum == 0, add triplet [-1,-1,2]	[[-1,-1,2]]	[-4, -1, -1, 0, 1, 2]
16	Skip duplicates left=3, right=4	1	3	4	-	-	[[-1,-1,2]]	[-4, -1, -1, 0, 1, 2]
17	Calculate sum	1	3	4	-1 + 0 + 1 = 0	sum == 0, add triplet [-1,0,1]	[[-1,-1,2], [-1,0,1]]	[-4, -1, -1, 0, 1, 2]
18	Skip duplicates left=4, right=3	1	4	3	-	-	[[-1,-1,2], [-1,0,1]]	[-4, -1, -1, 0, 1, 2]
19	left >= right, move to next i	2	-	-	-	-	[[-1,-1,2], [-1,0,1]]	[-4, -1, -1, 0, 1, 2]
20	Set i=2 (skip duplicate -1)	2	-	-	-	-	[[-1,-1,2], [-1,0,1]]	[-4, -1, -1, 0, 1, 2]
21	Set i=3	3	-	-	-	-	[[-1,-1,2], [-1,0,1]]	[-4, -1, -1, 0, 1, 2]
22	Set left=4, right=5	3	4	5	-	-	[[-1,-1,2], [-1,0,1]]	[-4, -1, -1, 0, 1, 2]
23	Calculate sum	3	4	5	0 + 1 + 2 = 3	sum > 0, right--	[[-1,-1,2], [-1,0,1]]	[-4, -1, -1, 0, 1, 2]
24	Update right=4	3	4	4	-	-	[[-1,-1,2], [-1,0,1]]	[-4, -1, -1, 0, 1, 2]
25	left >= right, move to next i	4	-	-	-	-	[[-1,-1,2], [-1,0,1]]	[-4, -1, -1, 0, 1, 2]
26	i=4 end (less than length-2 condition fails)	-	-	-	-	-	[[-1,-1,2], [-1,0,1]]	[-4, -1, -1, 0, 1, 2]

💡 i reaches 4, condition i < length-2 (4 < 4) is false, loop ends

Variable Tracker

Variable	Start	After Step 2	After Step 12	After Step 13	After Step 19	After Step 21	Final
i	-	0	1	1	2	3	4
left	-	-	1	2	3	4	-
right	-	-	5	5	4	5	-
Triplets Found	[]	[]	[]	[[-1,-1,2], [-1,0,1]]	[[-1,-1,2], [-1,0,1]]	[[-1,-1,2], [-1,0,1]]	[[-1,-1,2], [-1,0,1]]

Key Moments - 3 Insights

Why do we skip duplicate values for i and left/right pointers?

Skipping duplicates prevents adding the same triplet multiple times. For example, at step 20, i=2 is skipped because nums[2] == nums[1], avoiding repeated triplets as shown in execution_table rows 15-18.

Why do we move left pointer when sum < 0 and right pointer when sum > 0?

Because the array is sorted, increasing left moves to a bigger number to increase sum, and decreasing right moves to a smaller number to decrease sum. This is shown in steps 4-10 where left increments when sum < 0.

Why does the loop stop when left >= right?

When left meets or passes right, all pairs for current i are checked. This is shown at steps 11 and 24 where left >= right causes moving to next i.

Visual Quiz - 3 Questions

Look at the execution_table at step 15, what triplet is added?

A [-4, 1, 2]

B [-1, 0, 1]

C [-1, -1, 2]

D [0, 1, 2]

💡 Hint

Check the 'Triplets Found' column at step 15 in execution_table

At which step does the left pointer first move because sum < 0?

A Step 23

B Step 4

C Step 15

D Step 17

💡 Hint

Look at the 'Action' column for sum < 0 and left++ in execution_table

If the array had no duplicates, how would the execution_table change?

A There would be no steps skipping duplicates

B The sum calculation would be different

C The array would not be sorted

D The pointers would not move

💡 Hint

Refer to steps 16 and 18 where duplicates are skipped in execution_table

Concept Snapshot

Three Sum Problem:
- Sort array first
- For each element i, use two pointers left=i+1 and right=end
- Calculate sum = nums[i]+nums[left]+nums[right]
- If sum == 0, add triplet and skip duplicates
- If sum < 0, move left++ to increase sum
- If sum > 0, move right-- to decrease sum
- Repeat until left >= right
- Return all unique triplets

Full Transcript

The Three Sum problem finds all unique triplets in an array that sum to zero. First, the array is sorted to allow two-pointer technique. For each element i, two pointers left and right scan the rest of the array. The sum of nums[i], nums[left], and nums[right] is checked. If sum is zero, the triplet is recorded and pointers skip duplicates. If sum is less than zero, left pointer moves right to increase sum. If sum is greater than zero, right pointer moves left to decrease sum. This continues until left meets or passes right. The process repeats for each i, skipping duplicates to avoid repeated triplets. The final result is a list of all unique triplets that sum to zero.

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