Sort First, Skip Duplicates, Fast & Slow

Two Pointers, lesson 3 of 3

Sort First, Skip Duplicates, Fast & Slow

Sort to unlock two pointers for k-sum, avoid duplicate answers, and meet fast/slow pointers.

13 min, 0 of 3 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

The input isn't sorted? Sort it. Sorting costs O(n log n), which is cheap next to the O(n²) or O(n³) brute force it replaces.

That unlocks k-sum problems. For 3Sum, fix the first number nums[i], then run the two-pointer pair search on everything to its right, looking for -nums[i]:

  • 2Sum on sorted data: O(n)
  • 3Sum: n choices × O(n) = O(n²)
  • 4Sum: fix two, then two pointers = O(n³)
Example

Fix one, squeeze the rest

The inner while is exactly the lesson-one pair search, just with nums[i] added to every sum.

Skipping duplicates. "Return all unique triplets" is where most bugs live. With repeated values the scan finds the same combination several times. Sorting puts equal values side by side, so you can skip them cheaply:

  • outer loop: if i > 0 and nums[i] == nums[i - 1]: continue (this first value was already tried)
  • after a match: move lo (and/or hi) past every copy of the value you just used

Skipping beats collecting into a set: no extra memory, and no hashing of tuples.

Quiz

This pair search has no duplicate skipping. What does it print?

Exercise

Unique pairs

Write unique_pairs(nums, target) that returns every distinct pair of values [a, b] with a <= b and a + b == target, using two different positions of nums. nums is unsorted and may contain repeats. Any order of pairs is fine, but no pair may appear twice.

unique_pairs([3, 1, 2, 3, 1, 2], 4) is [[1, 3], [2, 2]].

Fast & slow pointers are the third shape: both move forward, but one takes two steps for every one step of the other. It's the go-to tool for cycles (you'll use it a lot in the Linked Lists unit):

  • no cycle: fast reaches the end first
  • a cycle: fast laps slow and they meet, since the gap between them shrinks by one every step

It works on any "next value" sequence, not just lists. A number is happy if repeatedly replacing it with the sum of its digits squared reaches 1; otherwise it loops forever.

Example

Happy numbers with fast & slow

No set of seen values: fast/slow detects the loop with O(1) memory. Print the sequence from step(4) to see the cycle 4 → 16 → 37 → ... → 4.

Quiz

Why are fast and slow pointers guaranteed to meet inside a cycle?