Skip to main content

15. 3Sum

medium

Find every unique triplet in an array that sums to zero. Tests sort-plus-two-pointer composition and the trickiest part — skipping duplicate triplets without missing any valid ones.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

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

Examples

Example 1

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

Explanation: The two unique triplets that sum to zero. Note that [-1,2,-1] is the same as [-1,-1,2] under set equality.

Example 2

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

Example 3

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Three nested loops is O(n^3) and the dedup is painful. Can you reduce one dimension?

Hint 2

Sort the array. Then for each i, the remaining problem is 'find two numbers in nums[i+1..] that sum to -nums[i]' — Two Sum II.

Hint 3

Skip duplicates at three points: when advancing i (skip equal to nums[i-1]), and after a hit, skip equal lefts and equal rights before re-entering the inner loop.

Solution approach

Reveal approach

Sort the array. For each index i from 0 to n-3, treat -nums[i] as the target and run a two-pointer search over nums[i+1..n-1]. Move left right when the sum is too small, right left when it's too large, and record on equality. After recording a hit, advance both pointers past any duplicate values to keep the result set unique. Also skip i forward if nums[i] equals nums[i-1] (avoids re-emitting triplets that start with the same first element). O(n log n) for the sort dominates the inner O(n) per i.

Complexity

Time
O(n^2)
Space
O(log n) to O(n) for sort

Related patterns

  • two-pointers
  • sorting

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Google
  • Microsoft
  • Apple

Practice these live with InterviewChamp.AI

Drill 3Sum and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →