Two pointers related algorithms

Некоторая вводная теория

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

Важное замечание – метод работает на монотонных функциях.

Например, вычисление суммы подмассивов, составленных из последовательных элементов. Допустим что входной массив составлен из неотрицательных элементов и отсортирован. left индекс первого элемента текущего подмассива, right – правого. Тогда при увеличении left сумма элементов не увеличится (либо не изменится, либо уменьшится), потому что за итерацию был исключен один элемент. При увеличении right сумма элементов не уменьшится, так как добавится один неотрицательный элемент. Поддерживая инварианты left <= right < n таким образом можно решить задачу о нахождении подмассива с суммой равной k, потому что на каждом шаге очевидно какой из индексов увеличивать в результате сравнения текущей суммы и k. Иначе – сигнализировать, что нет ответа.

Иными словами, зависимость суммы подмассива от изменения каждого из параметров по отдельности (а на итерации мы увеличиваем только один из индексов) “двигается” только в одном из направлений. Знак у этой функции не изменяется, это и есть монотонность.

Разбор задач

Leetcode 11. Container with most water

Пусть есть подмассив arr[left:right], right - left > 0, right <= n. Тогда ответ на задачу это максимум min(arr[left], arr[right]) * (right - left) для всех возможных пар индексов.

Задачу можно решить за O(n^2) просто перебрав все left и right удовлетворяющие условиям выше в двух вложенных циклах.

Для того чтобы решить задачу за линейное время, необходимо найти монотонность и обосновать переход. Положим left = 0, right = n - 1, то есть берем массив целиком. При сдвиге любой из границ на 1 за итерацию, правый множитель строго уменьшается. Это значит, что если arr[left] < arr[right], то мы потенциально можем увеличить левый множитель только за счет увеличения минимума среди двух элементов. Необходимо за итерацию пробовать увеличить меньший граничный элемент путем инкремента для left если arr[left] < arr[right] и декремента для right в противном случае.

Решение

public int maxArea(int[] height) {
  int left = 0, right = height.length - 1, maxArea = 0;
  while (right - left > 0) {
    maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
    if (height[left] < height[right]) {
        left++;
    } else {
        right--;
    }
  }
  return maxArea;
}

Сложность O(n) по времени, O(1) по памяти

Leetcode 2824. Count Pairs Whose Sum is Less than Target

Отсортируем массив чисел, сделав входную последовательность монотонной. Чтобы минимизировать сумму элементов, один из них должен быть заведомо наименьшим (наименьшим из непросмотренных), поэтому положим left = 0. Следующее наблюдение заключается в том, что если для некоторого right (left < right) nums[left] + nums[right] < target, то для всех индексов i: left < i < right nums[left] + nums[i] < target тоже верно, так как последовательность nums монотонна. Количество таких пар right - left. Указатель right необходимо инициализировать наибольшим значением, так как все наименьшие и удовлетворяющие будут учтены при выполнении условия nums[left] + nums[right] < target, иначе итеративно сдвинем right на 1 влево.

Решение

public int countPairs(List<Integer> nums, int target) {
    Collections.sort(nums);
    int left = 0, right = nums.size() - 1, ans = 0;
    while (left < right) {
        if (nums.get(left) + nums.get(right) < target) {
            ans += right - left;
            left++;
        } else {
            right--;
        }
    }
    return ans;
}

Сложность O(nlogn) по времени (сортировка), O(1) по памяти.