How do you solve 3Sum?

Sort the array. Iterate through each element as the first element of the triplet, skipping duplicates. For each fixed element, use two pointers (left and right) to find pairs that sum to the negative of the fixed element. Move pointers inward based on the sum comparison, skipping duplicates to avoid repeated triplets. Collect all valid triplets in the result list.

3Sum

Q: What is the time complexity of 3Sum?

O(n^2). Sorting takes O(n log n). The main loop runs O(n) times, and for each iteration, the two-pointer search runs in O(n), resulting in O(n^2) overall.

Q: What pattern does 3Sum use?

The Pattern: Two Pointers (Sorted Array Pair Search) The Heuristic: When searching for pairs that sum to a target in a sorted array, use two pointers starting at opposite ends and move inward based on the sum comparison; this approach efficiently finds all pairs in O(n) time and can be extended to triplets by fixing one element and searching pairs for the complement.

Medium Two Pointers

Problem

Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0.

0 ≤ nums.length ≤ 3000
−10⁵ ≤ nums[i] ≤ 10⁵

Example

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

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

First, the array is sorted to [-4,-1,-1,0,1,2]. The algorithm iterates through each number as a potential first element of the triplet. At index 1 (value -1), it uses two pointers starting at indices 2 and 5 to find pairs that sum with -1 to zero. The pair (nums[2], nums[5]) = (-1, 2) sums to 1, so the right pointer moves left. Eventually, the pair (-1, 2) is found, forming the triplet [-1, -1, 2]. The algorithm skips duplicates by checking if the current number equals the previous one. This process continues, finding the second triplet [-1, 0, 1]. The key is sorting and skipping duplicates to avoid repeated triplets.

Approach

Straightforward Solution

A brute-force approach would check all triplets with three nested loops, resulting in O(n^3) time complexity, which is too slow for large inputs.

Core Observation

The problem requires finding triplets that sum to zero without duplicates. Sorting the array enables efficient two-pointer scanning for pairs that complement the current element to zero, and also allows easy skipping of duplicates to ensure unique triplets.

Path to Optimal

Preview

Sorting the array allows fixing one element and searching for the other two using two pointers moving inward from both ends of the remaining array. This reduces the complexity to O(n^2)…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Sort the array. Iterate through each element as the first element of the triplet, skipping duplicates…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n^2)

Sorting takes O(n log n). The main loop runs O(n) times, and for each iteration, the two-pointer search runs in O(n), resulting in O(n^2) overall.

Space

O(n)

The sorting algorithm requires O(n) space in the worst case. The output list space is not counted as auxiliary space.

Pattern Spotlight

Two Pointers (Sorted Array Pair Search)

When searching for pairs that sum to a target in a sorted array, use two pointers starting at opposite ends and move inward based on the sum comparison; this approach efficiently finds all pairs in O(n) time and can be extended to triplets by fixing one element and searching pairs for the complement.

Solution

Python

1class Solution:
  def threeSum(self, nums: list[int]) -> list[list[int]]:
      res = []
      nums.sort()
5
      for i, a in enumerate(nums):
          if i > 0 and a == nums[i - 1]:
              continue
9
          l, r = i + 1, len(nums) - 1
          while l < r:
              three_sum = a + nums[l] + nums[r]
              if three_sum > 0:
                  r -= 1
              elif three_sum < 0:
                  l += 1
              else:
                  res.append([a, nums[l], nums[r]])
                  l += 1
                  while l < r and nums[l] == nums[l - 1]:
                      l += 1
      return res

Step-by-Step Solution

Sort the Array and Initialize Result Container

3res = []
4nums.sort()

Objective

To prepare the input for efficient two-pointer searching and store the resulting triplets.

Key Insight

Sorting the array is essential because it enables the two-pointer technique to find pairs summing to a target in linear time. Initializing the result list upfront provides a container to accumulate valid triplets.

Interview Quick-Check

Core Logic

Sorting transforms the problem into a structured search space where two pointers can efficiently find pairs summing to a target.

State & Boundaries

The result list must be initialized before iteration to collect all valid triplets.

Iterate Over Array, Skipping Duplicate Fixed Elements

To select each unique element as the first element of potential triplets while avoiding duplicate work.

Use Two Pointers to Find Complementary Pairs for Each Fixed Element

To find all pairs in the remaining array that sum with the fixed element to zero, efficiently and without duplicates.

Return the List of Unique Triplets

To output the final collection of all unique triplets found.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 7 Critical

if i > 0 and a == nums[i - 1]:

Skip the current element if it is the same as the previous to avoid duplicates.

Skipping duplicates at the fixed element prevents generating identical triplets multiple times, ensuring uniqueness in the result.

Line 17 Critical

else:

If the sum equals zero, a valid triplet is found.

This condition identifies the core success case where the three numbers sum to zero, ready to be recorded.

Line 20 Critical

while l < r and nums[l] == nums[l - 1]:

Skip duplicate elements at the left pointer to avoid repeated triplets.

This loop prevents adding triplets with the same second element multiple times, ensuring uniqueness.

Full line-by-line criticality + rationale for all 18 lines available on Pro.

Test Your Understanding

Why is it necessary to skip duplicates both when fixing the first element and when moving the left pointer?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct 3Sum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the 3Sum drill

or drill a free problem

1	`class Solution:`
2	`def threeSum(self, nums: list[int]) -> list[list[int]]:`
3	`res = []`
4	`nums.sort()`
5
6	`for i, a in enumerate(nums):`
7	`if i > 0 and a == nums[i - 1]:`
8	`continue`
9
10	`l, r = i + 1, len(nums) - 1`
11	`while l < r:`
12	`three_sum = a + nums[l] + nums[r]`
13	`if three_sum > 0:`
14	`r -= 1`
15	`elif three_sum < 0:`
16	`l += 1`
17	`else:`
18	`res.append([a, nums[l], nums[r]])`
19	`l += 1`
20	`while l < r and nums[l] == nums[l - 1]:`
21	`l += 1`
22	`return res`