Three Sum

The Three Sum problem on LeetCode is a well-known algorithmic problem that asks you to find all unique triplets in an array of integers that sum up to a specific target value. In other words, given an array of numbers, the task is to find all combinations of three numbers from the array such that their sum equals a given target value.

Problem Statement: Given an array nums of n integers, find all unique triplets (a, b, c) in the array such that a + b + c = 0. The solution set must not contain duplicate triplets.

Solving this problem typically involves writing an efficient algorithm that avoids duplicates and has a time complexity better than O(n^3). A common approach is to sort the array and use two-pointer techniques to find the triplets efficiently.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums, int target) {
  vector<vector<int>> result; // to store the final answer
  sort(nums.begin(), nums.end()); // sort the array in ascending order
  int n = nums.size(); // get the size of the array

  for (int i = 0; i < n - 2; i++) { // loop through the array from 0 to n-3
    if (i > 0 && nums[i] == nums[i-1]) continue; // skip duplicates for the first element
    int left = i + 1; // set the left pointer to i+1
    int right = n - 1; // set the right pointer to n-1

    while (left < right) { // loop until left and right pointers meet
      int sum = nums[i] + nums[left] + nums[right]; // calculate the sum of the triplet
      if (sum == target) { // if the sum is equal to the target
        result.push_back({nums[i], nums[left], nums[right]}); // add the triplet to the result
        left++; // move the left pointer to the right
        right--; // move the right pointer to the left

        while (left < right && nums[left] == nums[left-1]) left++; // skip duplicates for the second element
        while (left < right && nums[right] == nums[right+1]) right--; // skip duplicates for the third element
      } else if (sum < target) { // if the sum is less than the target
        left++; // move the left pointer to the right
      } else { // if the sum is greater than the target
        right--; // move the right pointer to the left
  return result; // return the final answer

int main() {
  vector<int> nums = {-1, 0, 1, 2, -1, -4}; // sample input array
  int target = 0; // sample target value
  vector<vector<int>> ans = threeSum(nums, target); // call the function with input array and target value
  for (auto v : ans) { // loop through the result vector
    for (auto x : v) { // loop through each triplet vector
      cout << x << " "; // print each element of the triplet
    cout << endl; // print a new line after each triplet
  return 0;

// Output:
// -1 -1 2 
// -1 0 1 

The algorithm runs in quadratic time, O(n^2), where n is the number of elements in the input array. This is mainly due to the two-pointer technique.

The space used by the algorithm is also quadratic, O(n^2), primarily because of the storage required for the result vector, which can hold up to O(n^2) triplets in the worst case.