How do you solve the 3Sum problem? | Interview Question

Q: How do you solve the 3Sum problem?

**Target Audience:** Beginners preparing for coding interviews — you should know what an array and a loop are; nothing else is assumed. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged `📌 Interview term:` with the exact vocabulary an interviewer expects. Every output quoted in the **Verified** section was printed by actually running the code shown with `python3`. ## 1. Why This Even Matters — A Story First Imagine a shop that sells weights, some positive (they push the scale down) and some negative (balloons that pull it up). A customer wants every different set of **exactly three items** that leaves the scale perfectly at zero. You could try every possible trio — with 1,000 items that is about 166 million trios. Or you could line the items up from lightest to heaviest, hold one item in your hand, and walk two fingers in from both ends of the shelf: if the scale tips down, move the right finger to

The problem

Question presented to candidate: "Given an array of integers, find all unique triplets that sum to zero. Each triplet should appear only once in the output, even if the array has duplicates. Please write it in Python and tell me the time and space complexity."

What a strong answer should cover:

Brute force is three nested loops, O(n³); the expected solution sorts first and then, for each anchor, runs a two-pointer scan: O(n²) time.
Why moving a pointer is safe on a sorted array: a too-small sum means the left value can never work with this anchor, a too-big sum means the right value cannot.
Duplicate handling by skipping equal neighbours (anchor and middle), instead of a set of results.
Early exit when the anchor is positive, and edge cases: fewer than three elements, all zeros.
Python specifics: sorted() returns a new list (the caller's list stays untouched) while list.sort() sorts in place; lists are unhashable, so a set-based dedupe needs tuples; Python integers never overflow.

Clarifying questions expected:

"Do you want values or indices?" — sorting loses the original indices.
"Must each distinct triplet appear once, and may I sort the input in place?"

Code / implementation expected: Yes — a three_sum(nums) function in Python that sorts once and runs a two-pointer scan per anchor.

arrays
two-pointers

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you should know what an array and a loop are; nothing else is assumed. Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged 📌 Interview term: with the exact vocabulary an interviewer expects. Every output quoted in the Verified section was printed by actually running the code shown with python3.

1. Why This Even Matters — A Story First

Imagine a shop that sells weights, some positive (they push the scale down) and some negative (balloons that pull it up). A customer wants every different set of exactly three items that leaves the scale perfectly at zero. You could try every possible trio — with 1,000 items that is about 166 million trios. Or you could line the items up from lightest to heaviest, hold one item in your hand, a

The solution is hidden so you can try first

5 min read · 10 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

Python3Sum with sort + two pointers on six inputs

Practice

PythonBrute force vs two pointers: same triplets, far less work

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.