3Sum — DSA Visualizer

Problem

Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] such that i≠j≠k and nums[i]+nums[j]+nums[k]==0. The solution set must not contain duplicate triplets.

Example 1

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

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

Constraints: 3 ≤ nums.length ≤ 3000 | −10⁵ ≤ nums[i] ≤ 10⁵

① Sort

›

② Fix Anchor

›

③ Two-Pointer Scan

›

④ Done

nums[i] —

nums[L] —

nums[R] —

sum ?

Sorting

Press Play to begin the animation.

Triplets Found

Variables

i (anchor)

—

L (left)

—

R (right)

—

sum

—

Step Logic

Press ▶ Play or Next Step to begin.

Ready 0 / 0

Select an example and press Play.

Algorithm

Sort the array — enables two-pointer technique

Fix anchor i; skip if nums[i]==nums[i-1] (duplicate)

Two pointers L=i+1, R=n-1; scan inward while L<R

sum=0 → save triplet + skip dups at L,R; sum<0 → L++; sum>0 → R--

Time

O(n²)

Space

O(1)

Why It Works

Why sort? After sorting, if sum is too small we know moving L right (to bigger values) will increase it. If sum is too large, moving R left decreases it. This eliminates guessing.

Why skip duplicates? After sorting, duplicates are adjacent. Skipping them at both anchor and pointer levels guarantees unique triplets without a HashSet.

Why O(n²)? O(n log n) sort + outer loop O(n) × inner two-pointer O(n) = O(n²) total. Each element is visited at most once per anchor.