Two Pointers Templates in Python
Alex Kang
Posted on August 12, 2022
What is two pointers technique?
Two pointer technique is using two pointers in an array to solve problems efficiently.
Templates
3 common two pointers techniques are:
- Sliding window
- Pointers from two ends
- Fast and slow pointers
Sliding Window
Sliding window can be used to search something in a subarray.
def get_counter():
pass
def condition():
pass
def do_something_before():
pass
def do_something_after():
pass
def sliding_window(arr):
counter = get_counter()
# outer loop to move end index
while end < len(arr):
end += 1
# start index only increase when condition
while condition():
do_something_before()
start += 1
do_something_after()
Pointers from two ends
Pointers from two ends can be used when the problem can be reduced to finding two elements in an array that satisfy a condition.
def condition_left():
pass
def condition_right():
pass
def do_something():
pass
def pointers_from_two_ends(arr):
left, right = 0, len(arr)-1
while left < right:
if condition_left():
left += 1
if condition_right():
right -= 1
do_something()
Fast and slow pointers
Fast and slow pointers can be used to:
- detect cycles
- remove duplicates
- find middle node
def condition_slow():
pass
def do_something():
pass
def fast_slow_pointers(arr):
slow = 0
for fast in range(len(arr)):
# only move slow pointer when condition
if condition_slow():
slow += 1
do_something()
💖 💪 🙅 🚩
Alex Kang
Posted on August 12, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
undefined GETTING STARTED WITH MACHINE LEARNING: A BEGINNER’S GUIDE USING SCIKIT-LEARN
November 29, 2024
