DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

3Sum

mediumTwo pointers Must-do

Problem statement

You are given a list of integers nums. Return every distinct group of three values, taken from three different positions, that adds up to 0. Each group should appear once, no matter how many positions could produce it. Groups and the order of values inside them can be in any order.

Examples

Example 1

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

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

Explanation: [-2, 1, 1] uses both 1s, which is allowed because they are at different positions.

Example 2

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

Output: [[0, 0, 0]]

Explanation: Many position choices give [0, 0, 0], but it is reported once.

Hints

Approach

Sort, fix the first value, and find the other two with two pointers. Skipping repeated values at every step means duplicates are never produced, so no set is needed.

  1. Sort the list.
  2. For each i: skip it if nums[i] equals nums[i - 1]. Stop early if nums[i] > 0, since three positive values cannot sum to 0.
  3. Set lo = i + 1 and hi to the last index.
  4. If the sum is below 0, move lo up. If above, move hi down.
  5. If it is 0, record the triple, move both pointers, then keep moving lo while it lands on the same value as before.

The space is O(1) beyond the output and the sort (Python's sort may use O(n) internally).

ComplexityTime O(n²)Space O(1) extra
Python
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
nums.sort()
result = []
n = len(nums)
for i in range(n - 2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
lo, hi = i + 1, n - 1
while lo < hi:
total = nums[i] + nums[lo] + nums[hi]
if total < 0:
lo += 1
elif total > 0:
hi -= 1
else:
result.append([nums[i], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
return result

Follow-up questions

  • Find the triple whose sum is closest to a given target.
  • Generalise to four values that sum to a target.

Frequently asked questions

Skipping lo past repeats is enough: with nums[i] and nums[lo] both fixed to new values, the third value is forced, so the same triple cannot be found again. Skipping hi as well is harmless and some people do both.

Not for the general case in any known simple way. O(n²) is the expected answer, and sorting first costs only O(n log n), which is smaller.

It tests whether you can reduce a problem to one you already know (Two Sum) and handle duplicates cleanly. Deduplicating results correctly matters in real tooling too, such as not raising the same alert twice for the same combination of hosts.