Examples / Two pointers▶Run in PyTrace
Two Pointers Visualization in Python
The two pointers technique keeps two indexes into the same array and moves them toward each other (or in the same direction) based on a comparison. On a sorted array it turns an O(n²) pair search into a single O(n) pass.
In this example, left starts at the smallest number and right at the largest. If their sum is too small, the only way to grow it is to move left forward; if it is too big, move right back.
ComplexityO(n) time, O(1) extra space.
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left + 1, right + 1]
if total < target:
left += 1
else:
right -= 1
return []Inputs
numbers[1,2,3,4,6,8,11,15]
target14
expected[3,7]
What to watch
leftandrightdrawn as colored pointers under thenumbersarray- The comparison
total < targetevaluated on every step, which decides which pointer moves - The search space shrinking by one cell per iteration