Skip to content

Volume ITechnology

4.5.3 — 3Sum ​

LeetCode 15 · Medium · ★ Blind 75

The problem ​

You are given an unsorted list of numbers called nums. Find every different group of three numbers in it that adds up to zero. Each group must use three different positions. The list can contain repeated values, but the answer must not contain the same group twice.

nums = [-1, 0, 1, 2, -1, -4]   →  [[-1, -1, 2], [-1, 0, 1]]
nums = [0, 1, 1]               →  []
nums = [0, 0, 0]               →  [[0, 0, 0]]

Look at the first example. There are two −1s in the list, and either one could pair with 0 and 1 to make [-1, 0, 1]. But that group appears only once in the answer. The "no repeated groups" rule is where all the difficulty is, not the adding up.

The list has between 3 and 3,000 numbers.

What the problem is really asking ​

Three numbers add to zero exactly when the first one equals minus the sum of the other two. So if you fix the first number, say −4, you need two more numbers that add up to 4. That is the problem from the last page, 4.5.2 Two Sum II.

So the question becomes: for each possible first number, find every pair after it that adds to its negative, without ever producing the same group twice.

The brute force, and where it wastes work ​

Try every group of three positions. To avoid repeats, sort each group and store it in a set.

python
def threeSum(nums):
    n = len(nums)
    found = set()
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    found.add(tuple(sorted((nums[i], nums[j], nums[k]))))
    return [list(t) for t in found]

Three loops inside each other try about \frac{n^3}{6} groups. For 3,000 numbers that is 4.5 billion groups. Far too slow.

The waste in one sentence: for each fixed pair i, j, the innermost loop searches the whole rest of the list for one known value, and the sorted-tuple set is a clumsy way of cleaning up repeats that a sorted list would never create.

The idea ​

Sort the list first. Sorting n numbers takes O(n \log n) time. That is cheap compared with the O(n^2) solution we are heading for, and it gives us two things.

  1. Two pointers work. Two Sum II needed a sorted list, and now we have one.
  2. Equal values sit next to each other. So skipping a repeat is as simple as asking "is this the same as the number just before it?"

Then the plan is:

  1. Fix the first number, nums[i], one position at a time.
  2. On everything to the right of i, run Two Sum II with two pointers, looking for pairs that add to -nums[i].
  3. Skip any value that would only rebuild a group we already found.

Think of a teacher grouping students whose scores add to zero. Picking three students at random is overwhelming. So the teacher lines everyone up by score, picks the first student, and says, "your score is −5, so I need two more whose scores add to +5." The teacher then uses the see-saw method from the last page on the rest of the line. A three-person problem has become a two-person problem the teacher already knows how to solve.

The solution ​

python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()                                            # (1)
        result = []

        for i in range(len(nums) - 2):                         # (2)
            if nums[i] > 0:                                    # (3)
                break
            if i > 0 and nums[i] == nums[i - 1]:               # (4)
                continue

            l, r = i + 1, len(nums) - 1                        # (5)
            while l < r:
                total = nums[i] + nums[l] + nums[r]            # (6)
                if total < 0:                                  # (7)
                    l += 1
                elif total > 0:
                    r -= 1
                else:                                          # (8)
                    result.append([nums[i], nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l - 1]:    # (9)
                        l += 1
                    while l < r and nums[r] == nums[r + 1]:
                        r -= 1

        return result
ts
function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);                                  // (1)
  const result: number[][] = [];

  for (let i = 0; i < nums.length - 2; i++) {                  // (2)
    if (nums[i] > 0) break;                                    // (3)
    if (i > 0 && nums[i] === nums[i - 1]) continue;            // (4)

    let l = i + 1, r = nums.length - 1;                        // (5)
    while (l < r) {
      const total = nums[i] + nums[l] + nums[r];               // (6)
      if (total < 0) l++;                                      // (7)
      else if (total > 0) r--;
      else {                                                   // (8)
        result.push([nums[i], nums[l], nums[r]]);
        l++;
        r--;
        while (l < r && nums[l] === nums[l - 1]) l++;          // (9)
        while (l < r && nums[r] === nums[r + 1]) r--;
      }
    }
  }
  return result;
}

Line by line ​

(1) Sort. In Python, nums.sort() sorts numbers by value. In TypeScript you must write nums.sort((a, b) => a - b). Without the little function, JavaScript sorts as text, comparing the first character first. So [10, 9] would stay [10, 9], because the text "1" comes before the text "9". The function (a, b) => a - b tells it to compare by value instead.

(2) Fix the first number. i goes from 0 up to the third-from-last position. We stop there because we need room for two more numbers after i.

(3) Stop once the fixed number is positive. The list is sorted, so if nums[i] is above zero, every number after it is also above zero. Three positive numbers can never add to zero. So we can stop the whole search. The answer would still be correct without this line, but it saves time.

(4) Skip a repeated first number. If nums[i] equals nums[i - 1], then every group starting with this value was already found when we fixed nums[i - 1]. Running again would only find the same groups a second time. The check i > 0 protects position 0, which has no number before it.

(5) Two pointers on the rest. l starts just after i, and r starts at the end.

(6) Add up the three numbers.

(7) Move a pointer, exactly as in Two Sum II. If the sum is below zero, we need bigger numbers, so l moves right. If it is above zero, r moves left.

(8) A match. Record the group. Then move both pointers inward, because both of those numbers have now been used with this nums[i].

(9) Skip repeated second and third numbers. After moving, l might land on the same value it just left. For example, after using a −1, the next number might also be −1. Using it would rebuild the same group. So we keep moving l while its value equals the one just before it. We do the mirror check for r, comparing with the value just after it.

This skip only appears inside the match branch, and that is on purpose. A repeated group can only be produced when we record a group. When the sum is simply too big or too small, moving one step is already correct, and the normal pointer moves will pass over repeats on their own.

Trace ​

Take nums = [-1, 0, 1, 2, -1, -4]. After sorting, it is [-4, -1, -1, 0, 1, 2], with positions 0 to 5.

iFixedPointer stepsGroups found
0−4needs a pair adding to 4. The biggest pair is 1 + 2 = 3, so l keeps moving right until it meets r.none
1−1l=2 (−1), r=5 (2): sum 0 → found. Move to l=3 (0), r=4 (1): sum 0 → found. Move, pointers cross.[-1, -1, 2], [-1, 0, 1]
2−1same as nums[1], so line (4) skips it—
30l=4 (1), r=5 (2): sum 3, too big, r moves left, pointers meetnone

Without line (4), i = 2 would fix the second −1 and find [-1, 0, 1] again, and the answer would contain it twice.

Complexity, derived ​

Time. Sorting takes O(n \log n).

The outer loop runs up to n times. For each i, the two pointers start at opposite ends of the rest of the list and move toward each other. Each step moves at least one pointer, and the skips in line (9) only move them further in the same direction. So for one i, the pointers take at most n steps in total. That is O(n) per i, and O(n) \times n = O(n^2) for the whole loop.

Adding the sort: O(n \log n) + O(n^2). For large n, n^2 grows much faster than n \log n, so the total is O(n^2).

Space. Apart from the answer, we only keep a few pointer variables, so the extra memory is O(1). One honest footnote: Python's built-in sort can use up to O(n) temporary memory while it works. Mention this if the interviewer is strict about space.

Edge cases ​

  • All zeros, such as [0, 0, 0, 0]. The first i finds [0, 0, 0]. Line (9) skips the other zeros for the pointers, and line (4) skips the other zeros for i. The answer is exactly [[0, 0, 0]].
  • No group works, such as [1, 2, 3]. Line (3) stops at once, because the first number is already positive. The answer is [].
  • Exactly three numbers. The outer loop runs once.

Changing the caller's list ​

nums.sort() changes the order of the list that was passed in. On a coding judge that does not matter. In real code it can cause a hard-to-find bug, because another part of the program might still be reading that list and not expect it to have moved.

If the list belongs to someone else, use sorted(nums) in Python, or [...nums].sort(...) in TypeScript. Both make a sorted copy and leave the original alone. The copy costs O(n) extra memory.

Variations you will meet ​

  • 3Sum Closest. Find the three numbers whose sum is closest to a target. Same loops, but you remember the closest sum seen. There is no repeat-skipping at all, which shows how much of 3Sum was really about repeats.
  • 4Sum. Add one more outer loop, with the same repeat-skip at each level. That is O(n^3).
  • 3Sum Smaller. Count the groups whose sum is below a target. When nums[i] + nums[l] + nums[r] is below the target, then every r between l + 1 and the current r also works with this l, because those numbers are even smaller. So you add r - l to the count in one step and move l. Counting a whole range at once is the useful idea there.

The general lesson: to solve a k-number sum, fix one number and solve the (k − 1)-number sum on the rest. The smallest case, two numbers, is two pointers.

What the interviewer will push on ​

"Why sort?" Give both reasons. Sorting makes two pointers possible, and it puts equal values side by side, so repeats are cheap to skip.

"Where exactly do you skip repeats, and why there?" Line (4) for the fixed number, and line (9) inside the match branch for the pair. Repeated groups can only appear when you record a group.

"Could you use a hash set instead of two pointers?" Yes. Fix two numbers and look up the third in a set. That is also O(n^2) time, but it uses O(n) memory, and removing repeated groups gets messy, because you end up sorting each group to use it as a key.

"Your sort changes the input list." Agree, and offer to sort a copy instead.

One thing to volunteer: say that the "no repeated groups" rule is the hard part of this problem, not the arithmetic. That observation shows you have actually written it.

Next: 4.5.4 Container With Most Water. Two pointers again, but now the rule for which pointer moves comes from geometry rather than from sorting.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet