Three Sum Problem All Unique Triplets in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Three Sum Unique Triplets Function

What is the output of the following C++ code that finds all unique triplets in the array which gives the sum of zero?

DSA C++

std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    std::sort(nums.begin(), nums.end());
    for (int i = 0; i < (int)nums.size() - 2; ++i) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int left = i + 1, right = (int)nums.size() - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.push_back({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;
}

int main() {
    std::vector<int> nums = {-1, 0, 1, 2, -1, -4};
    auto triplets = threeSum(nums);
    for (auto &triplet : triplets) {
        for (int num : triplet) {
            std::cout << num << " ";
        }
        std::cout << "-> ";
    }
    std::cout << "null" << std::endl;
    return 0;
}

A -1 -1 2 -> -1 0 1 -> null

B -1 0 1 -> -1 -1 2 -> null

C -1 2 -1 -> 0 1 -1 -> null

D -1 1 0 -> -1 2 -1 -> null

💡 Hint

Remember the function sorts the array and skips duplicates to find unique triplets summing to zero.

The function sorts the input array and uses a two-pointer approach to find triplets that sum to zero. It skips duplicates to ensure unique triplets. The output prints the triplets in sorted order as found: [-1, -1, 2] and [-1, 0, 1].

🧠 Conceptual

intermediate

Number of Unique Triplets in Three Sum

Given the input array nums = [3, -2, 1, 0, -1, 2, -1], how many unique triplets sum to zero?

A 3

B 5

C 4

D 2

💡 Hint

Try to find all sets of three numbers that add up to zero without repeating the same triplet.

The unique triplets are: [-2, -1, 3], [-2, 0, 2], [-1, -1, 2], [-1, 0, 1]. So total unique triplets are 4.

🔧 Debug

advanced

Identify the Error in Three Sum Implementation

What error will the following code produce when run?

DSA C++

std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    std::sort(nums.begin(), nums.end());
    for (int i = 0; i < (int)nums.size() - 2; ++i) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int left = i + 1, right = (int)nums.size() - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.push_back({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;
}

int main() {
    std::vector<int> nums = {0, 0, 0};
    auto triplets = threeSum(nums);
    for (auto &triplet : triplets) {
        for (int num : triplet) {
            std::cout << num << " ";
        }
        std::cout << "-> ";
    }
    std::cout << "null" << std::endl;
    return 0;
}

A No output (empty result)

B 0 0 0 -> null

C Runtime error due to out-of-bounds access

D Infinite loop

💡 Hint

Check how the code handles duplicates and the case when all elements are zero.

The code correctly finds the triplet [0, 0, 0] that sums to zero and outputs it. No errors or infinite loops occur.

📝 Syntax

advanced

Identify the Syntax Error in Three Sum Code

Which option contains a syntax error in the three sum function?

DSA C++

std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    std::sort(nums.begin(), nums.end());
    for (int i = 0; i < (int)nums.size() - 2; ++i) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int left = i + 1, right = (int)nums.size() - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.push_back({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;
}

A Using curly braces {} instead of parentheses () in push_back call

B Missing semicolon after ++left in the inner while loop

C Incorrect comparison operator in if (sum == 0)

D Missing return statement at the end of the function

💡 Hint

Check the syntax of push_back with initializer list in C++.

Using curly braces {} inside push_back is valid in C++11 and later for initializer lists. However, if the compiler does not support it or if the code is older style, it may cause syntax error. The other options are incorrect because semicolons are present, comparison operator is correct, and return statement exists.

🚀 Application

expert

Optimizing Three Sum for Large Input

You have a very large array with millions of integers. Which approach is the most efficient to find all unique triplets that sum to zero?

A Use recursion to generate all triplets and check their sums

B Use a brute force triple nested loop checking all triplets

C Use a hash map to store all pairs and then check for the third element

D Sort the array and use two pointers for each element to find pairs summing to the negative of that element

💡 Hint

Consider time complexity and how sorting helps reduce it.

Sorting the array and using two pointers for each element reduces the time complexity to O(n^2), which is efficient for large inputs compared to brute force O(n^3). Hash map approach can be less efficient due to extra space and complexity. Recursion for all triplets is very inefficient.

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. Find the triplet with the smallest product

D. Find pairs that sum to zero

Solution

1. Step 1: Understand the problem statement

   The problem asks to find all unique sets of three numbers in the array whose sum equals zero.

2. Step 2: Clarify uniqueness and sum condition

   Each triplet must be unique (no duplicates) and the sum of the three numbers must be exactly zero.

3. Final Answer:

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

4. Quick Check:

   Unique triplets with sum zero = Find all unique triplets that sum to zero [OK]

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

Common Mistakes:

• Confusing pairs with triplets
• Ignoring uniqueness of triplets
• Looking for max or min sums instead of zero sum

2. Which of the following C++ code snippets correctly sorts the input vector nums before applying the two-pointer technique in the Three Sum problem?

easy

A. std::sort(nums);

B. sort(nums, nums + nums.size());

C. nums.sort();

D. std::sort(nums.begin(), nums.end());

Solution

1. Step 1: Identify correct sorting syntax for std::vector

   For a vector, sorting requires iterators: nums.begin() and nums.end().

2. Step 2: Check each option

   std::sort(nums.begin(), nums.end()); uses correct syntax. sort(nums, nums + nums.size()); is invalid because nums is a vector, not a pointer array. nums.sort(); is invalid because vector has no sort() method. std::sort(nums); is invalid because std::sort requires two iterators.

3. Final Answer:

   std::sort(nums.begin(), nums.end()); -> Option D

4. Quick Check:

   Correct vector sorting = std::sort(nums.begin(), nums.end()); [OK]

Hint: Use iterators with std::sort for vectors [OK]

Common Mistakes:

• Using pointer syntax on vectors
• Calling sort() as a vector method
• Passing only one argument to std::sort

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

std::vector<int> nums = {-1, 0, 1, 2, -1, -4};
std::vector result;
std::sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++) {
  if (i > 0 && nums[i] == nums[i-1]) continue;
  int left = i + 1, right = nums.size() - 1;
  while (left < right) {
    int sum = nums[i] + nums[left] + nums[right];
    if (sum == 0) {
      result.push_back({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--;
    }
  }
}
for (auto &triplet : result) {
  for (int num : triplet) std::cout << num << ' ';
  std::cout << '\n';
}

medium

A. No output

B. -1 -1 2
-1 0 1

C. -4 -1 2
-1 0 1

D. -1 0 1
0 1 2

Solution

1. Step 1: Sort the array and initialize pointers

   Sorted array: [-4, -1, -1, 0, 1, 2]. Loop through each element with two pointers to find triplets summing to zero.

2. Step 2: Identify unique triplets with sum zero

   Triplets found are [-1, -1, 2] and [-1, 0, 1]. These are printed line by line.

3. Final Answer:

   -1 -1 2 -1 0 1 -> Option B

4. Quick Check:

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

Hint: Sort first, then use two pointers to find zero sum triplets [OK]

Common Mistakes:

• Not skipping duplicates
• Incorrect pointer movement
• Printing wrong triplets

4. Identify the bug in the following code snippet for the Three Sum problem:

std::vector<int> nums = {-2, 0, 1, 1, 2};
std::vector result;
std::sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++) {
  int left = i + 1, right = nums.size() - 1;
  while (left < right) {
    int sum = nums[i] + nums[left] + nums[right];
    if (sum == 0) {
      result.push_back({nums[i], nums[left], nums[right]});
      left++;
      right--;
    } else if (sum < 0) {
      left++;
    } else {
      right--;
    }
  }
}

medium

A. Missing check to skip duplicate i values

B. Incorrect sorting of the input vector

C. Wrong initialization of pointers left and right

D. Using push_back instead of emplace_back

Solution

1. Step 1: Analyze duplicate handling for i

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

2. Step 2: Confirm other parts are correct

   Sorting is correct, pointers are initialized properly, and push_back is valid here.

3. Final Answer:

   Missing check to skip duplicate i values -> Option A

4. Quick Check:

   Skipping duplicates for i avoids repeated triplets [OK]

Hint: Always skip duplicate i to avoid repeated triplets [OK]

Common Mistakes:

• Not skipping duplicates for i
• Skipping duplicates only for pointers
• Assuming sorting fixes duplicates automatically

5. Given the input array nums = {0, 0, 0, 0}, what is the correct output of the Three Sum problem that finds all unique triplets summing to zero?

hard

A. []

B. [[0, 0, 0], [0, 0, 0]]

C. [[0, 0, 0]]

D. [[0, 0]]

Solution

1. Step 1: Understand the input with duplicates

   All elements are zero, so the only triplet summing to zero is [0, 0, 0].

2. Step 2: Ensure uniqueness of triplets

   Even though multiple zeros exist, only one unique triplet [0, 0, 0] should be returned.

3. Final Answer:

   [[0, 0, 0]] -> Option C

4. Quick Check:

   Unique triplet with zeros = [[0, 0, 0]] [OK]

Hint: Multiple zeros produce one unique triplet [OK]

Common Mistakes:

• Returning duplicate triplets
• Returning pairs instead of triplets
• Returning empty result for all zeros