💬 Discord
Sign In
NeetCode #200LC-15MediumTwo PointersBlind 75NC 150NC 250
← Back to All Problems

#200 · #15 · 3Sum(三数之和)

📌 Problem Statement & Constraints

Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] with i < j < k such that the three sum to zero. The solution set must not contain duplicate triplets. Constraints: 3 <= nums.length <= 3000, -10^5 <= nums[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. Sort the array first. Then fix the first element nums[i] and solve a two-sum problem on the suffix with target -nums[i] using two pointers.
  2. Deduplication is the crux: skip i values that equal the previous one, and after finding a triplet, advance both pointers past any equal values.
  3. The sorted order makes the two-pointer scan valid: too small means move the left pointer right, too large means move the right pointer left.
  4. Early exit: once nums[i] > 0, no further triplets can sum to zero, since the remaining values are all positive.

💻 Benchmark Python3 Implementation

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res = []
        for i in range(n - 2):
            if nums[i] > 0:                # all remaining values are positive
                break
            if i > 0 and nums[i] == nums[i - 1]:
                continue                   # skip duplicate first elements
            l, r = i + 1, n - 1
            target = -nums[i]
            while l < r:
                s = nums[l] + nums[r]
                if s == target:
                    res.append([nums[i], nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1             # skip duplicate left values
                    while l < r and nums[r] == nums[r + 1]:
                        r -= 1             # skip duplicate right values
                elif s < target:
                    l += 1
                else:
                    r -= 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): the sort is O(n log n) and the outer loop with an inner two-pointer scan is O(n^2).
💾 Space Complexity
O(1) extra beyond the output and the sort's internal space.

⚠️ Interview Pitfalls & Follow-ups

  • Not deduplicating: [-1, 0, 1, 1]-style inputs would produce repeated triplets. Three separate dedup steps are needed (the outer index, the left pointer and the right pointer).
  • Using a set of sorted tuples for deduplication: it works but is O(n) extra space and hides the logic; in-place skipping is the standard answer.
  • Forgetting the nums[i] > 0 early break: it is an optimisation, not a correctness requirement, but it avoids scanning a pointless suffix.
  • Using a hash map for the inner two-sum: it would reintroduce duplicate handling complexity and O(n) space.
  • Sorting inside the loop: the sort must happen once, before the outer loop.