mafeshsho8lmafeshsho8l
Get Started
All coding questions

3Sum

medium
Blind 75NeetCode 150arraystwo-pointerssorting

Problem

Given a list of integers, find every unique triple of values that sums to zero. Return the list of triples without duplicates.

Examples

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Two distinct triples sum to zero.
Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]
The single zero triple.

Constraints

  • • 3 <= nums.length <= 3000
  • • -10^5 <= nums[i] <= 10^5
  • • Triples must be unique
Hints(tap to reveal)
  • 1. Sort first, then fix one value and two-pointer the rest.
  • 2. Skip duplicate values to avoid repeated triples.
Optimal approach(spoiler)
  1. Sort the array so duplicates are adjacent and pointers behave.
  2. Fix each value as the first of the triple, skipping repeats.
  3. Use two pointers on the remaining suffix to find pairs summing to its negation.
  4. Advance pointers past duplicates after recording a triple.
  5. O(n^2) time, O(1) extra space beyond the output.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor