How do you solve 3Sum, and why do you sort the input first?
You sort the numbers first, and then you use the two pointers technique for every first number.
def three_sum(nums):
values = sorted(nums)
triples = []
for i in range(len(values) - 2):
if i > 0 and values[i] == values[i - 1]:
continue
left, right = i + 1, len(values) - 1
while left < right:
total = values[i] + values[left] + values[right]
if total == 0:
triples.append((values[i], values[left], values[right]))
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return triples
So why do you sort first? Two reasons, and the first one is the important one.
The first reason is that the two pointers technique needs a sorted list. The pointers only work because you can tell which way to move them from a comparison, and that only works when the order is known.
The second reason is that sorting groups the duplicates together. Once the numbers are in order, every copy of the same number is next to the others, so you can step over them in one go. Without the sorting you would have to check every earlier answer to see whether you have already found it.
And there is one more benefit. Sorting also puts the copy of the list you are working on in a new list, so the list that the caller gave you is not changed. That is often what you want in an interview, because the question usually says that the input should not be modified.
The last question in this topic looks at the two pointers part and at the duplicates.