AI Hints
Home›DSA in Python Tutorial›Arrays and Lists
DSA in Python · Lesson 15 of 132

Two Pointers

One from each end.

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

Many array problems have a beautiful trick. Keep two positions, called pointers. Often one starts at the beginning and one at the end, and they walk towards each other. It turns slow nested loops into one fast pass.

Two Pointers
From the video: Two Pointers
  • Keep two positions
  • One at each end
  • Walk towards each other

Pair with a target sum

Here's a classic. In a sorted list, find two numbers that add up to a target. Left starts at the beginning, and right at the end. If the pair is too small, move left up, to a bigger number. If it's too big, move right down. Run it. Three and eleven make fourteen, and we only walked through the list once. That's O of N, instead of O of N squared.

two_pointers.pypython
def pair_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return nums[left], nums[right]
        if total < target:
            left += 1
        else:
            right -= 1
    return None

print(pair_sum([1, 3, 4, 6, 8, 11], 14))
Output
(3, 11)

When to use two pointers

Reach for two pointers when the data is sorted, or when you're comparing things from both ends, like in a palindrome. It's also handy for reversing a list in place, merging two sorted lists, and removing duplicates. The clue is usually, sorted data, and pairs.

keyvalue
Sorted datapairs with a target
Both endspalindromes
In placereversing
Two listsmerging

Summary

Two pointers walk through an array from both ends, turning O of N squared into O of N. Next, practice. Reversing a list, the two pointer way.

Key takeaways
  • left and right
  • Move one each step
  • O(n) instead of O(n²)
Next up: Practice: Reverse in Place — no extra list