13. 3Sum

MediumTwo PointersAlso on LeetCode ↗

Return every unique triplet [a, b, c] from nums (three different positions) with a + b + c = 0. The output must not contain duplicate triplets; any order is fine.

Example 1

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

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

Example 2

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

Output: [[0,0,0]]

Constraints

3 ≤ nums.length ≤ 3000

Hint 1

Sort first. Fix the first number, then the problem becomes Two Sum II on the rest.

Hint 2

Skip equal neighbours to avoid duplicate triplets.

Two PointersSorting

Reference solution for Sort + two pointers (time O(n²), space O(1) extra). Each solution passes every test in all four languages.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue                       # skip duplicate first values
            lo, hi = i + 1, len(nums) - 1
            while lo < hi:
                s = nums[i] + nums[lo] + nums[hi]
                if s < 0:
                    lo += 1
                elif s > 0:
                    hi -= 1
                else:
                    res.append([nums[i], nums[lo], nums[hi]])
                    lo += 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1                # skip duplicate second values
                    hi -= 1
        return res

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i + 2 < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int lo = i + 1, hi = nums.length - 1;
            while (lo < hi) {
                int s = nums[i] + nums[lo] + nums[hi];
                if (s < 0) lo++;
                else if (s > 0) hi--;
                else {
                    res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                    lo++;
                    while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
                    hi--;
                }
            }
        }
        return res;
    }
}

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        int n = nums.size();
        for (int i = 0; i + 2 < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int lo = i + 1, hi = n - 1;
            while (lo < hi) {
                int s = nums[i] + nums[lo] + nums[hi];
                if (s < 0) lo++;
                else if (s > 0) hi--;
                else {
                    res.push_back({nums[i], nums[lo], nums[hi]});
                    lo++;
                    while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
                    hi--;
                }
            }
        }
        return res;
    }
};

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const res = [];
  for (let i = 0; i + 2 < nums.length; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let lo = i + 1, hi = nums.length - 1;
    while (lo < hi) {
      const s = nums[i] + nums[lo] + nums[hi];
      if (s < 0) lo++;
      else if (s > 0) hi--;
      else {
        res.push([nums[i], nums[lo], nums[hi]]);
        lo++;
        while (lo < hi && nums[lo] === nums[lo - 1]) lo++;
        hi--;
      }
    }
  }
  return res;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Language