AI Hints
Home›DSA in Python Tutorial›Interview Method
DSA in Python · Lesson 105 of 132

Practice: Three Sum

Sort, then two pointers.

⏱ 2 min read▶ Video at 2:05:41🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Find every set of three numbers in a list that add up to zero, without repeating the same set twice. It's a famous step up from two sum. Pause. Could sorting, and two pointers, help?

Practice: Three Sum
From the video: Practice: Three Sum
  • Three numbers that sum to zero
  • No repeated sets
  • Sort, then two pointers?

Fix one, search for two

First we sort. Then we fix one number at a time, and use two pointers on the rest to find a pair that cancels it out. Skipping numbers equal to the previous one prevents duplicate answers. Run it. Two triplets, minus one, minus one, two, and minus one, zero, one.

three_sum.pypython
def three_sum(nums):
    nums, out = sorted(nums), []
    for i in range(len(nums) - 2):
        if i and nums[i] == nums[i - 1]: continue
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0: lo += 1
            elif s > 0: hi -= 1
            else:
                out.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                while lo < hi and nums[lo] == nums[lo - 1]: lo += 1
    return out

print(three_sum([-1, 0, 1, 2, -1, -4]))
Output
[[-1, -1, 2], [-1, 0, 1]]

Building on two sum

Three sum is two sum, with one number fixed. Sorting costs O of N log N, and the loop with two pointers costs O of N squared, so that's the total. Interviewers love this kind of question, because it rewards seeing an old problem inside a new one.

keyvalue
SortO(n log n)
Fix oneouter loop
Two pointersinner search
TotalO(n²)

Summary

Sort, fix one number, and use two pointers to find the other two, skipping duplicates. Next, the best stretch of a list, with Kadane's algorithm.

Key takeaways
  • Sort first
  • Fix one, two pointers for the rest
  • Skip duplicates
Next up: Practice: Maximum Subarray — Kadane's algorithm