3Sum

Return all unique triplets [a, b, c] from the array such that a + b + c = 0.

A way to picture it

Line everyone up by height. Pin one friend in place, then send two more walking in from opposite ends of the line toward each other. Total too small? The left walker steps up to someone bigger. Too big? The right walker steps down.

How to approach it

Sort, then for each pinned number run a two-pointer search for a pair summing to its negative. Skip repeated values to avoid duplicate triplets.

Example

Input: {"nums":[null,0,1,2,null,null]}. Output: [[null,null,2],[null,0,1]].

Complexity: O(n²) time and O(1) extra space. Sorting is O(n log n); each pin runs one O(n) two-pointer sweep.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.