3Sum

Medium#15towards each other

You get an array of numbers. Find every triple of numbers from three different places in the array that adds up to 0. Each triple goes into the answer once, even if the array lets you build it in several ways. Our example: [2, -2, 0, 1, -1, -2] — the answer is [-2, 0, 2] and [-1, 0, 1].

15 3SumWalkthrough · 1×

Example: [2, -2, 0, 1, -1, -2], sorted into [-2, -2, -1, 0, 1, 2]. i fixes one number, left and right walk towards each other looking for the other two.

0-21-22-1304152before sorting2-201-1-2
the fixed number nums[i]the pair under left and rightstill possibleruled out or skippeda triple with sum 0

Sort: [2, -2, 0, 1, -1, -2] becomes [-2, -2, -1, 0, 1, 2]. Equal numbers now stand side by side

01/59
restart · back · play · step
Speed
1function threeSum(nums):
2 sort(nums)
3 triples = []
4 for i from 0 to len(nums) - 3:
5 if i > 0 and nums[i] == nums[i - 1]:
6 continue
7 left = i + 1
8 right = len(nums) - 1
9 while left < right:
10 sum = nums[i] + nums[left] + nums[right]
11 if sum < 0:
12 left = left + 1
13 else if sum > 0:
14 right = right - 1
15 else:
16 t = [nums[i], nums[left], nums[right]]
17 add t to triples
18 left = left + 1
19 right = right - 1
20 while left < right and nums[left] == t[1]:
21 left = left + 1
22 return triples
state
i
–
nums[i]
–
left
–
right
–
sum
–
t
–
triples
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Fix one number, nums[i], and the other two must add up to -nums[i]. In a sorted array that is Two Sum II: left and right walk towards each other, and each move rules a number out for good.
  2. After sorting, equal numbers stand side by side, so a repeat is easy to spot. If nums[i] equals the number before it, its triples are already found and i skips it; after a found triple, left steps over the copies of its middle number the same way.
  3. Each triple is found once, when i first stands on its smallest number: the loop tries every first number, and the pair search sees every pair to the right of it.

Complexity

Time O(n²): sorting takes O(n log n), then for each of the n values of i the pointers cross the rest of the array once. Memory O(1) not counting the answer: the array is sorted in place, and no set is needed to catch repeats.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.