[/dsa/leetcode]

15 - 3Sum

Wednesday, 16 September 2026

<medium> [problem]

Fix one element, then run the sorted two pointer scan on the rest, skipping equal values to keep triplets unique.

{array}{two pointers}{sorting}

Problem

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

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

Input: nums = [0,1,1]
Output: []

Input: nums = [0,0,0]
Output: [[0,0,0]]

Constraints:

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

Approach

Sort the given array so that the smallest element comes at first. this way we can skip any number that is bigger than 0 and also deal with duplicates. We start from i = 0 -> n - 2 (as j and k would be next two elements). Now that first element is decided, we can make two pointer = i + 1, k = n - 1, and condition according to the question sum = nums[i] + nums[j] + nums[k]. This just turns into a modified binary search (we already sorted the array).

  • sum > 0: the sum is too big and nums[j] is already the smallest value in range, so nums[k] can’t be in any triplet with this j. k--.
  • sum < 0: nums[j] is too small to pair with anything left. j++.
  • sum == 0: record the triplet, then move both pointers. Moving just one can never sum to 0 again and shrinking the window from one side alone strictly changes the sum in one direction.

Two cheap cuts on the outer loop: once nums[i] > 0 every remaining element is positive and no triplet can reach 0, so break. And if nums[i] == nums[i - 1] this i would regenerate every triplet the previous one already produced, so skip it.

After recording a hit sum == 0, inorder to prevent duplicates we walk from both sides j and k increment and decrement pointers respectively until there are no duplicates.

nums = [-2, 0, 0, 0, 2, 2], i = 0 (-2)
j=1 k=5  ->  -2 + 0 + 2 = 0   push {-2,0,2},  j++ k--
j=2 k=4  ->  -2 + 0 + 2 = 0   push {-2,0,2}   <- same triplet again
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        const int n = nums.size();
        vector<vector<int>> res;

        for (int i = 0; i < n - 2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum > 0) {
                    k--;
                } else if (sum < 0) {
                    j++;
                } else {
                    res.push_back({nums[i], nums[j], nums[k]});
                    j++;
                    k--;
                    while (j < k && nums[j] == nums[j - 1]) j++;
                    while (j < k && nums[k] == nums[k + 1]) k--;
                }
            }
        }
        return res;
    }
};
  • time: O(n^2) — O(n log n) to sort, then an O(n) scan for each of the n choices of i
  • space: O(1) ignoring the output and whatever the sort uses
quantinium © 2026