Два вказівники та sliding window: як перетворити O(n²) на O(n)

Half the easy/medium задач на масивах на співбесідах розв'язується одним прийомом: тримаємо два індекси і рухаємо їх залежно від порівняння. Ключова властивість — кожен вказівник монотонний: він рухається лише в один бік і ніколи не повертається. Тому сумарна кількість кроків обмежена довжиною масиву — і наївний вкладений цикл за O(n²) перетворюється на один прохід за O(n).

«Два вказівники» — це насправді парасолька над кількома різними патернами. Їх легко сплутати, бо всі тримають два індекси, але правила руху різні. У цій статті розберемо чотири основні: злиття, протилежні кінці, read/write і ковзне вікно.

1. Злиття двох відсортованих масивів

Дано два відсортовані масиви A і B. Треба отримати один відсортований масив C за O(n + m). Очевидний варіант — склеїти і відсортувати — працює за O((n+m)·log(n+m)) та ігнорує те, що входи вже відсортовані. Правильне спостереження: найменший елемент C — це або A[0], або B[0], тобто фронт одного з масивів. Забрали переможця — і наступний кандидат знову на фронті. Тримаємо вказівник i в A та j в B, порівнюємо і просуваємо той, чий елемент менший:

def merge(a, b):
    n, m = len(a), len(b)
    i, j = 0, 0
    c = [0] * (n + m)

    while i < n or j < m:
        take_from_a = (j == m) or (i < n and a[i] <= b[j])
        if take_from_a:
            c[i + j] = a[i]
            i += 1
        else:
            c[i + j] = b[j]
            j += 1
    return c

Кожна ітерація просуває рівно один вказівник: i — не більше n разів, j — не більше m разів. Разом рівно n + m ітерацій.

Деталь, яку часто пропускають: у порівнянні стоїть a[i] <= b[j], а не строге <. Це дає стабільність: рівні елементи з A потрапляють у C раніше за рівні елементи з B — стандартна конвенція merge sort, і саме тому цей цикл є серцем merge sort.

2. Протилежні кінці

Другий патерн: один вказівник на початку, другий у кінці, рухаються назустріч.

Two Sum на відсортованому масиві (LeetCode 167). Знайти пару з сумою target. Три випадки: сума дорівнює target — знайшли; менша — потрібні більші значення, рухаємо l вправо; більша — рухаємо r вліво:

def two_sum(numbers, target):
    l, r = 0, len(numbers) - 1
    while l < r:
        s = numbers[l] + numbers[r]
        if s == target:
            return [l + 1, r + 1]
        elif s < target:
            l += 1
        else:
            r -= 1

Чому ми нічого не пропускаємо? Коли сума завелика і ми відступаємо r, елемент numbers[r] не може бути частиною жодної відповіді з поточним l або будь-яким l правіше: масив відсортований, тож усі такі суми ще більші. Симетричний аргумент працює для l. Кожен крок безпечно викреслює один елемент з розгляду — тому O(n).

3. Read/write: фільтрація на місці

Третій патерн: обидва вказівники рухаються вправо, але з різною швидкістю. read сканує кожен елемент, write позначає наступний вільний слот для «прийнятого» елемента і відстає. Інваріант: усе в [0, write) — це збережений префікс уже переглянутої частини.

Move Zeroes (LeetCode 283): пересунути всі нулі в кінець, зберігши порядок ненульових елементів, in-place:

def move_zeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1

Той самий скелет розв'язує Remove Duplicates from Sorted Array (LeetCode 26) і будь-яку задачу виду «залишити елементи з властивістю X, не виділяючи новий масив». Цей патерн живе і поза співбесідами: mark-compact garbage collector проходить купу рівно так само. Вказівник scan класифікує об'єкти на живі та мертві, вказівник free позначає слот, куди переїде наступний живий об'єкт. Один прохід O(n) — і живі об'єкти ущільнені в суцільний префікс, а за ними один великий вільний блок.

4. Sliding window: найдовший відрізок із сумою ≤ S

Тепер головний патерн. Дано масив додатних чисел. Знайти найдовший підвідрізок із сумою не більше S.

Перебір усіх O(n²) відрізків — надто повільно. Вікно рятує завдяки монотонності: оскільки всі елементи додатні, сума лише зростає при розширенні. Тому якщо відрізок [l, r] «поганий» (сума > S), то і [l, r+1] поганий; а якщо [l, r] «хороший», то і [l+1, r] хороший. Звідси ключовий факт: оптимальна ліва межа для кожної правої рухається тільки вправо.

Алгоритм: розширюємо вікно вправо, і щойно сума перевищила S — зсуваємо l, доки інваріант не відновиться:

def longest_segment_sum_leq(a, s):
    l = 0
    curr_sum = 0
    max_len = 0
    for r in range(len(a)):
        curr_sum += a[r]                  # розширили вікно
        while curr_sum > s:               # відновлюємо інваріант
            curr_sum -= a[l]
            l += 1
        max_len = max(max_len, r - l + 1) # вікно [l..r] хороше
    return max_len

Кожен елемент заходить у вікно один раз і виходить один раз — амортизовано O(n), попри вкладений while. Бонус: якщо замість max_len писати count += r - l + 1, той самий цикл рахує кількість хороших відрізків. Після стабілізації вікна l — найменша валідна ліва межа, тому рівно r − l + 1 хороших відрізків закінчуються в r.