Problem Overview

We are given an integer array nums, We need to find all unique triplets [nums[i], nums[j], nums[k]] such that:

  • i != j, i != k, j != k
  • nums[i] + nums[j] + nums[k] == 0
  • We need to return unique triplets
  • Notice that the order of the output and the order of the triplets does not matter.

LeetCode - Three Sum

Example

Input: [-1, 0, 1, 2, -1, -4]
Output: [[-1,-1,2], [-1,0,1]]

Explanation:

  • (-1) + (-1) + 2 = 0 // First
  • (-1) + 0 + 1 = 0 // Second
  • (-1) + 2 + (-1) = 0 // Third

As we can see multiple triplets produces their sum to 0, we only have to return unique triplets either (first, second) or (second, third).

Brute Force Approach

Idea

  • We Use three nested loops.
  • Try every possible triplet every loop.
  • If sum == 0, we add that triplet to result.

Code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        int n = nums.size();
        vector<vector<int>> result;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        result.push_back({nums[i], nums[j], nums[k]});
                    }
                }
            }
        }

        return result;
    }
};

Why This Fails

  1. Time Complexity: O(n³) → Will fail for large inputs.

  2. Duplicates: It does not prevent duplicate triplets. To fix that we need to use set, which adds extra overhead.

Optimal Approach — Convert to Two Sum

Key Insight

If we fix one number, the problem becomes: similar to what we did in two sum to convert it to single element search.

Find two numbers in the remaining array that such that all elements sums to 0. This only works after sorting.

Step-by-Step Strategy

  1. Sort the array.
  2. Fix one element at index i.
  3. Use two pointers:
    • l = i + 1
    • r = n - 1
  4. Move pointers based on sum.
  5. Run duplicated skip logic once we found are triplet.

Optimized Code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        int n = nums.size();
        vector<vector<int>> result;

        sort(nums.begin(), nums.end());

        for (int i = 0; i < n; i++) {

            // Skip duplicate fixed elements
            if (i > 0 && nums[i] == nums[i - 1])
                continue;

            int l = i + 1;
            int r = n - 1;

            while (l < r) {

                int sum = nums[i] + nums[l] + nums[r];

                if (sum > 0) {
                    r--;
                } 
                else if (sum < 0) {
                    l++;
                } 
                else {
                    result.push_back({nums[i], nums[l], nums[r]});

                    // Skip duplicate left values
                    while (l < r && nums[l] == nums[l + 1])
                        l++;

                    // Skip duplicate right values
                    while (l < r && nums[r] == nums[r - 1])
                        r--;

                    l++;
                    r--;
                }
            }
        }

        return result;
    }
};

Time & Space Complexity

Time Complexity

  • Sorting → O(n log n)
  • Outer loop → O(n)
  • Two pointer scan → O(n)

Overall: 👉 O(n²)

Space Complexity

  • No extra data structures used.
  • Sorting is in-place (ignoring recursion stack).

👉 O(1) auxiliary space 👉 O(n) only if counting output space

Why Two Pointer Works

After sorting:

  • If sum is too large → move right pointer left.
  • If sum is too small → move left pointer right.
  • Because array is sorted, this guarantees linear scan per fixed element.

That’s what reduces O(n³) → O(n²).

Using set + unordered_set

Idea

  • Fix one number.
  • Use hash set to find complement.
  • Store sorted triplets in a set to avoid duplicates.

Why It’s Not Ideal

  • Inserting vectors into a set is expensive.
  • Sorting each triplet adds overhead.
  • Overall still roughly O(n²), but with heavy constants.
  • Messy logic for duplicate control.

Works — but not clean.

Final Takeaways

  • Try to to fix one value and find the remaining in problem like two sum and three sum.
  • To use two pointer search the array must be sorted.