all Python 3Algorithms & data structuresfunction

Two pointers

techniques

Two indices move towards each other or in the same direction. O(n) for problems on sorted arrays.

Syntax

lo, hi = 0, len(arr)-1
while lo < hi: ...

The converging variant is correct only on sorted data; hand it an unsorted list and it quietly returns a wrong answer. Sorting it yourself costs O(n log n) and destroys the original positions, so when the task asks for indices a one-pass dict usually wins. Watch the loop boundary too: while lo < hi keeps an element from being paired with itself, while lo <= hi allows it.

Examples

# Сумма двух чисел в отсортированном массиве
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr)-1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target: return (lo, hi)
        elif s < target: lo += 1
        else: hi -= 1
    return None
print(two_sum_sorted([1,2,3,4,6], 6))  # → (1, 3) (это 2+4)

# Проверка палиндрома
def is_palindrome(s):
    lo, hi = 0, len(s)-1
    while lo < hi:
        if s[lo] != s[hi]: return False
        lo += 1; hi -= 1
    return True
print(is_palindrome('racecar'))  # → True
print(is_palindrome('hello'))    # → False

# Удаление дубликатов in-place
def remove_dups(arr):
    if not arr: return 0
    slow = 0
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    return slow + 1
arr = [1,1,2,3,3,4]
k = remove_dups(arr)
print(arr[:k])  # → [1,2,3,4]

# Слияние двух отсортированных массивов
def merge_sorted(a, b):
    i = j = 0; result = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]: result.append(a[i]); i+=1
        else: result.append(b[j]); j+=1
    result.extend(a[i:]); result.extend(b[j:])
    return result
print(merge_sorted([1,3,5],[2,4,6]))  # → [1,2,3,4,5,6]

# Контейнер с наибольшим объёмом
def max_area(heights):
    lo, hi = 0, len(heights)-1
    best = 0
    while lo < hi:
        area = (hi-lo) * min(heights[lo],heights[hi])
        best = max(best, area)
        if heights[lo] < heights[hi]: lo+=1
        else: hi-=1
    return best
print(max_area([1,8,6,2,5,4,8,3,7]))  # → 49

See also

Common errors

Open in the full glossarydocs.python.orgReport an inaccuracy