Three Sum Problem All Unique Triplets in DSA C# - Time & Space Complexity

Time Complexity: Three Sum Problem All Unique Triplets

O(n²)

Understanding Time Complexity

We want to understand how the time needed grows when finding all unique triplets that sum to zero in an array.

How does the number of steps change as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public IList> ThreeSum(int[] nums) {
    Array.Sort(nums);
    var result = new List>();
    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) {
                result.Add(new List{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 result;
}
    

This code finds all unique triplets in the array that add up to zero by sorting and using two pointers.

Identify Repeating Operations

• Primary operation: The outer loop runs through each element, and inside it, a two-pointer while loop scans the remaining elements.
• How many times: Outer loop runs about n times; inner while loop runs up to n times for each outer iteration.

How Execution Grows With Input

As the array size grows, the number of steps grows roughly with the square of the input size.

Input Size (n)	Approx. Operations
10	About 100 steps
100	About 10,000 steps
1000	About 1,000,000 steps

Pattern observation: The steps increase very fast as input grows, roughly by n times n, which is quadratic growth.

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows roughly with the square of the input size, so doubling the input makes the work about four times bigger.

Common Mistake

[X] Wrong: "The time complexity is O(n³) because there are three nested loops."

[OK] Correct: The inner two-pointer loop moves inward without restarting fully each time, so it runs in total about n times per outer loop, not n² times, making the total O(n²).

Interview Connect

Understanding this time complexity helps you explain how to handle problems with multiple loops efficiently and shows you can analyze nested loops carefully.

Self-Check

"What if the input array was already sorted? How would that affect the time complexity?"

Practice

1. What is the main goal of the Three Sum Problem All Unique Triplets in an integer array?

easy

A. Find all unique triplets that sum to zero

B. Find the maximum sum of any three numbers

C. Sort the array in ascending order

D. Count the number of pairs that sum to zero

Solution

1. Step 1: Understand the problem statement

   The problem asks to find all unique groups of three numbers (triplets) in the array whose sum equals zero.

2. Step 2: Clarify the output requirement

   We must return all such triplets without duplicates, not just count or sort.

3. Final Answer:

   Find all unique triplets that sum to zero -> Option A

4. Quick Check:

   Goal = unique triplets summing to zero [OK]

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

Common Mistakes:

• Confusing triplets with pairs
• Trying to find max sum instead of zero sum
• Ignoring uniqueness of triplets

2. Which of the following C# code snippets correctly initializes an integer array named nums for 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 List<int> { -1, 0, 1, 2, -1, -4 };

Solution

1. Step 1: Check array initialization syntax in C#

   Correct syntax for array initialization is: int[] nums = new int[] { ... };

2. Step 2: Validate each option

   int[] nums = new int[] { -1, 0, 1, 2, -1, -4 }; uses correct syntax. int nums = { -1, 0, 1, 2, -1, -4 }; misses array type. int[] nums = (-1, 0, 1, 2, -1, -4); uses parentheses instead of braces. int[] nums = new List<int> { -1, 0, 1, 2, -1, -4 }; tries to assign a List to an array variable.

3. Final Answer:

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

4. Quick Check:

   Array init syntax = int[] nums = new int[] { -1, 0, 1, 2, -1, -4 }; [OK]

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

Common Mistakes:

• Using parentheses instead of braces
• Assigning List to array variable
• Missing type declaration

3. What is the output of the following C# code snippet that finds all unique triplets summing to zero?

int[] nums = { -1, 0, 1, 2, -1, -4 };
var result = ThreeSum(nums);
foreach(var triplet in result) {
    Console.WriteLine(string.Join(", ", triplet));
}

// Assume ThreeSum returns List of unique triplets

medium

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

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

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

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

Solution

1. Step 1: Sort and find triplets summing to zero

   Sorted array: [-4, -1, -1, 0, 1, 2]. Triplets summing to zero are [-1, -1, 2] and [-1, 0, 1].

2. Step 2: Match output with options

   [-1, 0, 1] [-1, -1, 2] lists these two triplets correctly. Others contain invalid or impossible triplets.

3. Final Answer:

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

4. Quick Check:

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

Hint: Sort array first, then find triplets with two-pointer [OK]

Common Mistakes:

• Not sorting before searching
• Including duplicate triplets
• Wrong triplet sums

4. Identify the bug in this C# code snippet for the Three Sum problem:

public IList ThreeSum(int[] nums) {
    var result = new List();
    Array.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) {
                result.Add(new List<int> { nums[i], nums[left], nums[right] });
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

medium

A. No check to skip duplicate values for i, left, and right

B. Array is not sorted before processing

C. Incorrect sum calculation formula

D. Using List instead of Array for result

Solution

1. Step 1: Analyze duplicate handling in loops

   The code does not skip duplicate values for i, left, or right, which can cause duplicate triplets in the result.

2. Step 2: Verify other parts

   Array is sorted, sum calculation is correct, and List usage is valid. So only duplicate skipping is missing.

3. Final Answer:

   No check to skip duplicate values for i, left, and right -> Option A

4. Quick Check:

   Missing duplicate skip = No check to skip duplicate values for i, left, and right [OK]

Hint: Always skip duplicates after finding a valid triplet [OK]

Common Mistakes:

• Not skipping duplicates causing repeated triplets
• Forgetting to sort array
• Wrong sum calculation

5. Given the input array nums = [-2, 0, 1, 2, -1, -1, 2], which of the following lists contains all unique triplets that sum to zero?

hard

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

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

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

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

Solution

1. Step 1: Sort the array and find triplets

   Sorted nums: [-2, -1, -1, 0, 1, 2, 2]. Valid unique triplets summing to zero are [-2, 0, 2], [-1, -1, 2], and [-1, 0, 1].

2. Step 2: Compare with options

   [[-2, 0, 2], [-1, -1, 2], [-1, 0, 1]] matches these triplets exactly. Others contain invalid or duplicate triplets.

3. Final Answer:

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

4. Quick Check:

   All unique triplets = [[-2, 0, 2], [-1, -1, 2], [-1, 0, 1]] [OK]

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

Common Mistakes:

• Including triplets with wrong sums
• Missing duplicates in output
• Ignoring sorting step