Два указателя (в одну сторону)

Два указателя (в одну сторону): как это работает?

Оба индекса стартуют с начала массива. read читает, а write помечает следующее место записи.

read сдвигается на каждом шаге цикла. Он смотрит каждый элемент ровно один раз.

Проверка решает, оставить ли текущее значение. Только эта проверка и меняется от задачи к задаче.

При сохранении значение копируется в ячейку write. После этого write сдвигается на один.

При отбрасывании write стоит на месте. Ячейка ждёт следующее выжившее значение.

write отстаёт от read ровно на число отброшенных. Поэтому начало массива до write и есть ответ.

Источники: Wikipedia (англ.): In-place algorithm

1. [3, 2, 3, 4, 2] write=0Убираем все тройки. arr[0] это тройка, поэтому запись не идёт.
2. [2, 2, 3, 4, 2] write=1arr[1] это двойка, она остаётся. Значение уходит в ячейку 0.
3. [2, 2, 3, 4, 2] write=1arr[2] это ещё одна тройка. write остаётся на месте.
4. [2, 4, 3, 4, 2] write=2arr[3] это четвёрка, она остаётся. Значение ложится в ячейку 1.
5. [2, 4, 2, 4, 2] write=3Последняя двойка ложится в ячейку 2. Ответ это длина 3.

function compact(arr) {
    let slow = 0;
    for (let fast = 0; fast < arr.length; fast++) {
        if (shouldKeep(arr[fast], arr[slow])) {
            arr[slow] = arr[fast];
            slow++;
        }
    }
    return slow; // new length
}

declare function shouldKeep(candidate: number, kept: number): boolean;

function compact(arr: number[]): number {
    let slow = 0;
    for (let fast = 0; fast < arr.length; fast++) {
        if (shouldKeep(arr[fast], arr[slow])) {
            arr[slow] = arr[fast];
            slow++;
        }
    }
    return slow; // new length
}

def compact(arr):
    slow = 0
    for fast in range(len(arr)):
        if should_keep(arr[fast], arr[slow]):
            arr[slow] = arr[fast]
            slow += 1
    return slow  # new length

function compact(array &$arr): int {
    $slow = 0;
    for ($fast = 0; $fast < count($arr); $fast++) {
        if (shouldKeep($arr[$fast], $arr[$slow])) {
            $arr[$slow] = $arr[$fast];
            $slow++;
        }
    }
    return $slow; // new length
}

    public static int compact(int[] arr) {
        int slow = 0;
        for (int fast = 0; fast < arr.length; fast++) {
            if (shouldKeep(arr[fast], arr[slow])) {
                arr[slow] = arr[fast];
                slow++;
            }
        }
        return slow; // new length
    }

    private static boolean shouldKeep(int candidate, int kept) {
        throw new UnsupportedOperationException("your rule here");
    }

    public static int Compact(int[] arr) {
        int slow = 0;
        for (int fast = 0; fast < arr.Length; fast++) {
            if (ShouldKeep(arr[fast], arr[slow])) {
                arr[slow] = arr[fast];
                slow++;
            }
        }
        return slow; // new length
    }

    private static bool ShouldKeep(int candidate, int kept) {
        throw new NotImplementedException("your rule here");
    }

Два указателя (в одну сторону): разбор примера

Оставить каждое значение не более двух раз

В отсортированном массиве значение может повторяться много раз. Обрежьте его так, чтобы каждое встречалось максимум дважды.

Работайте в том же массиве и верните новую длину.

Первые два значения проходят всегда, две копии разрешены.

Дальше оставляйте arr[read], только если оно отличается от arr[write - 2]. В той ячейке лежит уже записанная вторая копия.

function removeDuplicatesII(nums) {
    let write = 0;

    for (let read = 0; read < nums.length; read++) {
        // nums[write - 2] is the copy two slots back in the output
        if (write < 2 || nums[read] !== nums[write - 2]) {
            nums[write] = nums[read];
            write++;
        }
    }

    return write; // new logical length
}

Два указателя (в одну сторону): когда применять?

Паттерн «Два указателя (в одну сторону)» нужен, когда в условии есть слова «удалить дубликаты на месте, сохранив порядок», «переместить/разбить элементы с сохранением порядка» или «сжать массив, используя O(1) дополнительной памяти». Решение на нём обычно укладывается в O(n).

• •удалить дубликаты на месте, сохранив порядок
• •переместить/разбить элементы с сохранением порядка
• •сжать массив, используя O(1) дополнительной памяти
• •сдвинуть нули или заданное значение в конец

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

Два указателя (в одну сторону): с чем путают?

Паттерн «Два указателя (в одну сторону)» чаще всего путают с этими паттернами: Преобразование массива на месте, Два указателя (с концов), Скользящее окно (переменное) и Быстрый и медленный указатели.

• Преобразование массива на месте (In-place array transform): Работа в одном буфере это цель. Отстающий указатель записи это один из способов её достичь.
• Два указателя (с концов) (Two pointers (opposite ends)): Те указатели стартуют по краям отсортированных данных и сходятся. Эти оба стартуют с нулевого индекса.
• Скользящее окно (переменное) (Sliding window (variable)): Окно тоже двигает два индекса вперёд, но хранит живой отрезок. Здесь отстающий индекс это место записи.
• Быстрый и медленный указатели (Fast & slow pointers): Там быстрый указатель делает два шага и ловит цикл. Здесь он делает один и читает.

Два указателя (в одну сторону): частые ошибки

• Дают write обогнать read

  Тогда копия затрёт данные, которые read ещё не видел. write двигается только при сохранении.

• Проверяют по исходному массиву

  Проверка идёт по arr[write - 1], последнему сохранённому значению. arr[read - 1] может быть уже затёрт.

• Сдвигают хвост при каждом удалении

  Линейный проход превращается в O(n в квадрате). Хватает одного копирования вперёд.

• Верят ячейкам после write

  В ячейках после write лежат старые значения, оставшиеся до прохода. Смысл имеют только первые write ячеек.

Два указателя (в одну сторону): задачи с собеседований

Паттерн «Два указателя (в одну сторону)» решает такие задачи с собеседований: Удаление дубликатов из отсортированного массива, Удаление элемента, Сдвиг нулей, Удаление дубликатов из отсортированного массива II, Сжатие строки, Является ли подпоследовательностью и Слияние отсортированных массивов.

• Удаление дубликатов из отсортированного массива: Оставляйте значение, только если оно отличается от arr[write - 1].
• Удаление элемента: Оставляйте всё, что не равно заданному значению.
• Сдвиг нулей: Скопируйте ненулевые вперёд, потом добейте хвост.
• Удаление дубликатов из отсортированного массива II: Проверка смотрит на две ячейки назад, а не на одну.
• Сжатие строки: Запишите символ, потом запишите длину его серии.
• Является ли подпоследовательностью: Один указатель идёт по короткой строке, другой по длинной.
• Слияние отсортированных массивов: Пишите с конца, тогда непрочитанное не затрётся.

Два указателя (в одну сторону): сложность по времени и памяти

У паттерна «Два указателя (в одну сторону)» целевая сложность O(n).

n до 1e6 даёт O(n) времени и O(1) памяти. Указатель чтения видит каждый элемент один раз.