Шаблон решения задач на Two Pointers.

Существенная часть задач на собеседованиях в FAANG-компании по алгоритмам - задачи на массивы, строки и связные списки.
Множество из них решается при помощи подхода, который называется Two Pointers.

Какие признаки того, что задача на Two Pointers?
1) В условии есть массив, строка или связный список (или данные задачи можно к ним свести).
2) Массив, строка или список в задаче отсортированны или их можно отсортировать (тогда сложность с линейной повысится до O(n*log(n)).
3) В условии не один массив/строка/список, а два.
4) По логике задачи вам надо суммировать/умножать или сравнивать разные элементы из одного и того же массива/строки/списка
5) Аналогично предыдущему, для случая если у вас два массива/строки/списка - по логике задачи вам нужно суммировать/умножать или сравнивать элементы из двух/нескольких массивов/строк/списков.
6) В условии сказано, что нужно найти пару, тройку, четверку чисел из заданного массива
7) В условии описываются интервалы времени, с которыми нужно что-то сделать (смержить по какому-то критерию, найти окно в расписании и т.д.)
8) В условии идет речь про палиндромы.
9) Нужно изменить массив/строку in-place (без дополнительных структур данных и доп. памяти).
10) Нужно смержить несколько массивов в один.

Метод Two Pointers сводится к тому, что вы идете циклом по вашему массиву/строке/списку при помощи не одного указателя/индекса, а при помощи двух указателей/индексов.

Типичный код, который циклом идет по массиву при помощи одного указателя i:

for (int i = 0; i < arr.length; i++) {
    ....
}

В методе Two Pointers, вам одновременно нужно использовать два указателя.

Тут может быть несколько вариантов в зависимости от задачи:

1) Массив один. Первый указатель вначале указывает на начало массива, а второй на конец массива. Указатели двигаются навстречу друг другу:

int left = 0;
int right = arr.length - 1;
while (left < right) {
    {calculate_something}
    {return_break_condition}
    if ({left_move_condition}) {
        {when_move_left_logic}
        left++;
    } else if ({right_move_condition}) {
        {when_move_right_logic}
        right--;
    }
}

{calculate_something} - какие-то вычисления или логика, специфичная для задачи.
{return_break_condition} - условие окончания работы алгоритма, если его можно прервать раньше, чем left станет равным или большим, чем right.
{left_move_condition} - условие, когда двигать левый указатель.
{right_move_condition} - условие, когда двигать правый указатель.
{when_move_left_logic} - какая-то доп. логика, если нужно ее выполнить, когда двигаем левый указатель.
{when_move_right_logic} - какая-то доп. логика, если нужно ее выполнить, когда двигаем правый указатель.
2) Массив один. Оба указателя вначале указывают на середину массива. Далее двигаются в противоположные стороны:

int left = (arr.length - 1)/2;
int right = (arr.length - 1)/2;
while (left >= 0 && right < arr.length) {
    {calculate_something}
    {return_break_condition}
    if ({left_move_condition}) {
        {when_move_left_logic}
        left--;
    } else if ({right_move_condition}) {
        {when_move_right_logic}
        right++;
    }
}

3) Массива два. Оба указателя начинают с начала первого и второго массива соответственно. В одном цикле идем по двум массивам одновременно:

int i = 0;
int j = 0;
while (i < arr1.length {&&/||} j < arr2.length) {
    {calculate_something}
    {return_break_condition}
    if ({i_move_condition}) {
        {when_move_i_logic}
        i++;
    } else if ({j_move_condition}) {
        {when_move_j_logic}
        j++;
    }
}

4) Список/Массив/Строка одна. Идем двумя указателями, которые стартуют с начала, но с разной скоростью. Fast and Slow Pointers.
Например, вначале подвинем первый указатель сразу на k-позиций. Далее будем двигать оба указателя с одной скоростью. Тогда вконце, один указатель будет сдвинут на k-позиций относительно первого.