What is the brute force approach and complexity for 3Sum?

Three loops; store each zero-sum triplet sorted in a set with time complexity O(N³ · log M) and space complexity O(M).

What is the optimal approach and complexity for 3Sum?

Sort; fix nums[i]; two pointers; skip equal values at every level with optimal time complexity O(N²) and space complexity O(1).

How do you identify the pattern for 3Sum?

Look for key signals in the prompt: "three values that add up to 0" indicates Fix one value, then the other two are a sorted pair-sum → Two Sum II.; "return the values, not the indices" indicates Positions don't matter, so we may sort.; "no duplicate triplets" indicates After sorting, repeats are neighbours → skip equal values at the fixed level and after each hit..

3Sum

Medium·LeetCode #15 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You are given an integer array nums.

Find every triplet of values [nums[i], nums[j], nums[k]], taken from three different positions, whose sum is 0.

Each triplet may appear only once in the answer. Two triplets count as the same if they hold the same three values, even if they came from different positions. The order of the triplets, and of the values inside them, does not matter.

Input

An integer array nums.

Output

A list of all unique triplets (as lists of 3 values) that add up to 0.

Example 1

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

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

−1 + 0 + 1 = 0 can be made with either of the two −1s, but it is listed only once. −1 + −1 + 2 = 0 uses both −1s.

Example 2

Input: nums = [0, 1, 1]

Output: []

The only triplet is 0 + 1 + 1 = 2.

Example 3

Input: nums = [0, 0, 0]

Output: [[0, 0, 0]]

The only triplet adds up to 0.

Constraints

• 3 ≤ nums.length ≤ 3000
• −10^5 ≤ nums[i] ≤ 10^5

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“three values that add up to 0”

→ Fix one value, then the other two are a sorted pair-sum → Two Sum II.

“return the values, not the indices”

→ Positions don't matter, so we may sort.

“no duplicate triplets”

→ After sorting, repeats are neighbours → skip equal values at the fixed level and after each hit.

Approach Complexity Ladder

Brute Force — every triplet + a setO(N³ · log M)O(M)

Three loops; store each zero-sum triplet sorted in a set

Better — fix one, hash set for the thirdO(N² · log M)O(N + M)

Fix nums[i]; for each j, look up the needed third value in a set

Optimal — sort, fix one, two pointers, skip duplicatesO(N²)O(1)

Sort; fix nums[i]; two pointers; skip equal values at every level

Brute Force Intuition

Try every i < j < k. When the three values add up to 0, sort those three values and put them in a set. The set throws away repeats, because the same three values always sort to the same list.

Recognition rule for this sub-pattern:

Sort, fix one element (or more), and solve the rest as a two-pointer pair problem. Skip duplicates carefully.

Remember this · Two Pointers

Trigger

Sorted array, pairs/triplets with a target, comparing from both ends, compacting an array in place.

Think

If I compare the elements at two positions, can I safely discard one side?

Key question

Which pointer moves, and why can the skipped elements never be the answer?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Two Pointers translate into production architectures and low-level memory mechanics.

LLD Architecture

Circular Buffer & Ring Queue

Two pointer read/write head synchronization in production memory pools.

Explore Track

C++ Internals

Pointers vs References Deep Dive

Pointer arithmetic, dereferencing semantics, and memory layout behind in-place array passes.

Explore Track

C++ Internals

const Correctness & East-Const

Passing read-only spans with const int* without copying buffers.

Explore Track

Triplet Sum in Array 3Sum Closest