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()
Top comments (0)