3Sum

medium Coding Interview Patterns 15–20 min

NumPy allowed · plain Python earns 10 bonus points

Interactive
Two Pointers & Sliding Window, Step by Step
Pattern
1
L
2
3
4
6
R
arr[L]=1 + arr[R]=6 = 7 vs target 6 -> too big, move R left
Step 1 / 3
Both modes run the exact algorithm described on the linked practice problem, one real step at a time -- not a pre-rendered animation. Edit the input and every step recomputes live.

Reduce an O(n^3) triplet search to O(n^2) by sorting and pairing an outer loop with two-pointer search, deduplicating elements cleanly.

Related Skills

Task

Implement three_sum(nums): find all unique triplets [a, b, c] that sum to zero. Return triplets sorted ascending, with the overall list of triplets sorted lexicographically.

Function Signature

three_sum(nums: list[int]) -> list[list[int]]

Examples

Example 1: Classic Six Element Array
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Example 2: No Triplet Exists
Input: nums = [0, 1, 1]
Output: []

Constraints

  • Libraries are allowed; a plain-Python solution earns 10 bonus points.
  • 3 <= len(nums) <= 3000.
  • Each triplet must be sorted ascending [a <= b <= c].
  • The solution set must not contain duplicate triplets.
Python3Saved ✓
def three_sum(nums: list[int]) -> list[list[int]]:
"""Return all unique triplets [nums[i], nums[j], nums[k]] such that
i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Each triplet must be sorted ascending, and the list of triplets
must be sorted lexicographically."""
# Your implementation here
pass

Case 1: Classic Six Element Array
Input: nums = [-1, 0, 1, 2, -1, -4]
Expected: [[-1, -1, 2], [-1, 0, 1]]
Case 2: No Triplet Exists
Input: nums = [0, 1, 1]
Expected: []