Two Pointers: Slow and Fast
Apply the slow-fast pointer pattern to remove duplicates in-place, move zeroes, and partition arrays around a pivot value.
Slow and Fast Pointers Explained
The slow-fast pointer pattern (also called tortoise-and-hare) uses two pointers moving at different speeds through the same sequence. Unlike opposite-ends pointers, both start at the beginning. The slow pointer advances one step at a time; the fast pointer advances two (or more). Their difference in speed creates useful invariants: the slow pointer tracks a 'valid prefix' while the fast pointer scans ahead for conditions.
# Slow pointer marks the write position;
# Fast pointer scans for next non-duplicate.
def remove_duplicates(nums):
if not nums: return 0
slow = 0 # next position to write a unique value
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1 # new length
nums = [1, 1, 2, 3, 3, 3, 4]
k = remove_duplicates(nums)
print(nums[:k]) # [1, 2, 3, 4]Remove Duplicates from Sorted Array
In a sorted array, duplicates are adjacent. The slow pointer tracks the last unique value written; the fast pointer scans ahead. Whenever the fast pointer reaches a value different from nums[slow], advance slow and copy the new value. This in-place algorithm runs in O(n) time with O(1) extra space — a standard interview question testing mastery of the read-write pointer pattern.
def remove_duplicates_v2(nums):
slow = 0
for fast in range(len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
# Allow at most 2 occurrences
def remove_duplicates_k2(nums):
slow = 0
for fast in range(len(nums)):
if slow < 2 or nums[fast] != nums[slow - 2]:
nums[slow] = nums[fast]
slow += 1
return slow
print(remove_duplicates_k2([1,1,1,2,2,3]))
# Result: 5, nums[:5] = [1,1,2,2,3]All lessons in this course
- Array Basics and In-Place Operations
- Prefix Sums and Running Totals
- Two Pointers: Opposite Ends
- Two Pointers: Slow and Fast