Python Two-Pointer Template
The two-pointer pattern walks two indices through a sorted array, moving them inward (or together) based on a comparison. It turns many naive O(n^2) problems into O(n) sweeps. This entry covers the inward-sweep template (two-sum sorted), the same-direction template (remove duplicates in place), and a 3-sum builder that uses two pointers as the inner loop.
930 views
4
def two_sum_sorted(nums, target):
"""Return (i, j) such that nums[i] + nums[j] == target, or None."""
lo, hi = 0, len(nums) - 1
while lo < hi:
total = nums[lo] + nums[hi]
if total == target:
return (lo, hi)
if total < target:
lo += 1 # need a bigger sum: shift left pointer right
else:
hi -= 1 # need a smaller sum: shift right pointer left
return None
nums = [1, 2, 4, 7, 11, 15]
print(two_sum_sorted(nums, 9)) # (1, 3) (2 + 7)
print(two_sum_sorted(nums, 26)) # (4, 5) (11 + 15, last two)
print(two_sum_sorted(nums, 3)) # (0, 1) (1 + 2, first two)
print(two_sum_sorted(nums, 100)) # None
print(two_sum_sorted([], 5)) # None (empty input)
print(two_sum_sorted([5], 5)) # None (single element, no pair)The classic two-pointer template starts pointers at the extremes and moves them inward based on the comparison. Because the array is sorted, increasing lo strictly increases the sum and decreasing hi strictly decreases it, so each move makes monotonic progress toward the target. The total runtime is O(n) because each pointer can move at most n steps. Reach for this whenever the input is sorted and the answer involves a pair (sum, difference, product) compared against a target.
def remove_duplicates(nums):
"""Compact `nums` so each value appears once. Return the new length."""
if not nums:
return 0
write = 0
for read in range(1, len(nums)):
if nums[read] != nums[write]:
write += 1
nums[write] = nums[read]
return write + 1
nums = [0, 0, 1, 1, 1, 2, 3, 3, 4]
length = remove_duplicates(nums)
print(length) # 5
print(nums[:length]) # [0, 1, 2, 3, 4]
# Edges.
empty = []
print(remove_duplicates(empty), empty) # 0 []
solo = [7]
print(remove_duplicates(solo), solo) # 1 [7]
all_same = [4, 4, 4, 4]
len_same = remove_duplicates(all_same)
print(len_same, all_same[:len_same]) # 1 [4]When both pointers move forward, the pattern becomes 'fast read, slow write'. The fast pointer scans every element once; the slow pointer only advances when a write actually happens. The result is an in-place compaction in O(n) time and O(1) extra space, which is what the LeetCode 'remove duplicates from sorted array' family expects. The same shape applies to 'move zeros to the end', 'remove all instances of a value', and 'partition by predicate': only the equality check inside the if changes.
def three_sum(nums):
"""All unique triplets that sum to zero, sorted within each triplet."""
nums = sorted(nums)
triplets = []
n = len(nums)
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicate first element
lo, hi = i + 1, n - 1
while lo < hi:
total = nums[i] + nums[lo] + nums[hi]
if total == 0:
triplets.append((nums[i], nums[lo], nums[hi]))
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1 # skip duplicate second element
while lo < hi and nums[hi] == nums[hi + 1]:
hi -= 1 # skip duplicate third element
elif total < 0:
lo += 1
else:
hi -= 1
return triplets
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [(-1, -1, 2), (-1, 0, 1)]
print(three_sum([0, 0, 0, 0])) # [(0, 0, 0)] (one triplet, dedup works)
print(three_sum([1, 2, 3])) # [] (no zero sum)
print(three_sum([])) # [] (empty input)3-sum reduces to a fixed outer index plus a two-pointer inner loop on the remaining sorted suffix. Sorting first costs O(n log n), and the inner sweep is O(n), so the total is O(n^2): better than the O(n^3) brute force. The duplicate-skip lines are the trickiest part: skip the outer index when it repeats a previous value, and skip both inner pointers after a hit so the same triplet does not get reported twice. The same outer-fix-plus-inner-two-pointer pattern handles 4-sum and the 'closest 3-sum' variants.