«Метод двух указателей» на примерах часто встречающихся задач на собеседованиях. Часть 1

Из 43 задач, собранных по знакомым разработчикам и открытым источникам, 12 были именно на технику «два указателя», т.е. составляли почти 30%.

1. Начнем с классической задачи «Слияние двух отсортированных массивов или списков»

Даны два отсортированных массива, необходимо получить третий отсортированный массив.

Идея подхода:
будем последовательно заполнять результирующий массив минимальными значениями из двух исходных массивов. А раз массивы отсортированы по возрастанию, то минимальное значение находится в самом начале массива, и нам каждый раз нужно сравнивать оба этих первых значения для выявления наименьшего из них, а не искать минимум среди всех элементов обоих массивов. Именно в этом заключается суть ускорения!

function merge_sorted(arr1, arr2) {
    let result = []
    while (arr1.length > 0 || arr2.length > 0) {
        if (arr1.length == 0)
            result.push(arr2.shift())
         else if (arr2.length == 0)
            result.push(arr1.shift())
        else if (arr1[0] <= arr2[0])
            result.push(arr1.shift())
        else
            result.push(arr2.shift())
    }
    return result
}

function merge_sorted(arr1, arr2) {
    let result = []
    let p1 = 0
    let p2 = 0
    while (p1 < arr1.length || p2 < arr2.length) {
        if (p1 == arr1.length) {
            result.push(arr2[p2])
            p2++
        } else if (p2 == arr2.length) {
            result.push(arr1[p1])
            p1++
        } else if (arr1[p1] <= arr2[p2]) {
            result.push(arr1[p1])
            p1++
        } else {
            result.push(arr2[p2])
            p2++
        }
    }
    return result
}

function merge_sorted(arr1, arr2) {
    let result = []
    let i1 = 0
    let i2 = 0
    while (i1 < arr1.length || i2 < arr2.length)
        if (i1 == arr1.length)
            result.push(arr2[i2++])
        else if (i2 == arr2.length || arr1[i1] <= arr2[i2])
            result.push(arr1[i1++])
        else
            result.push(arr2[i2++])
    return result
}

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def merge(l1, l2):
    pre_head = ListNode()
    curr = pre_head

    while l1 or l2:
        if not l1:
            curr.next = l2
            l2 = l2.next
        elif not l2:
            curr.next = l1
            l1 = l1.next
        elif l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next

        curr = curr.next

    return pre_head.next

Поэтому, если на интервью вам попалась задачка слить два массива или списка, то можно дать следующие рекомендации:

1. Не сокращайте кол-во условий и инкрементов в процессе (пока вы не написали и не отладили весь алгоритм), иначе можно легко запутаться.
2. Не забывайте проверять условия достижения конца массива или списка одним из указателей или индексов.
3. Пишите самую объемную, но наглядную версию. Потом, при необходимости, удалите избыточность.
4. Верно обосновывайте алгоритмическую сложность. Каждый индекс пробегает последовательно значения от 0 до length ровно один раз - значит сложность по времени O(n). В случае со списками, поскольку мы не создаем новые узлы, расход памяти будет O(1).

2. Навстречу друг другу

Дан массив целых чисел и число target. Необходимо вернуть индексы двух значений, которые в сумме дают target. При этом каждый элемент может использоваться только один раз. А само задание так же имеет ровно одно решение (т.е. возвращаем первые попавшиеся индексы, удовлетворяющие условию)

Классическое решение подразумевает использование хэш-таблицы, в которую мы заносим элементы исходного массива. Мы так же ищем второе слагаемое для каждого элемента массива, но делаем это не линейным поиском за O(n) в массиве, а поиском в хэштаблице за О(1) и получаем общую сложность O(n). Сама хеш-таблица подготавливается так же за O(n), что не влияет на общую сложность, которая остается O(n).

def two_sum(arr, target):
    hash = {}
    for (i, val) in enumerate(arr):
        hash[val] = i
        
    for (i, val) in enumerate(arr):
        second_add = target - val
        # Ищем второе слагаемое в хэштаблице и проверяем,
        # что не складываем элемент с самим собой.
        if second_add in hash and hash[second_add] != i:
            return [i, hash[second_add]

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

Итого, на каждом шаге мы либо двигаем левый индекс вправо, либо правый влево. То есть индексы двигаются навстречу друг другу.

def two_sum(arr, target):
    left = 0
    right = len(arr) - 1

    while left < right:
        if arr[left] + arr[right] == target:
            return [left, right]
        if arr[left] + arr[right] < target:
            left += 1
        else:
            right -= 1

def two_sum_with_sort(arr, target):
    # Преобразуем массив в набор пар (значение, оригинальный индекс).
    arr = [(val, i) for i, val in enumerate(arr)]
    # Сортируем по значению.
    arr.sort(key = lambda x: x[0])

    # Теперь каждый элемент отсортированного массива хранит пары, первое значение которой можно получить так arr[i][0],  
    # а оригинальный индекс так arr[i][1].
        
    left = 0
    right = len(arr) - 1

    while left < right:
        if arr[left][0] + arr[right][0] == target:
            return [arr[left][1], arr[right][1]]
        if arr[left][0] + arr[right][0] < target:
            left += 1
        else:
            right -= 1

Дан массив целых чисел, нужно вернуть сумму любых двух значений, максимально близкую к указанной, но меньше ее. Если такой суммы не существует, то вернуть -1.

Пример 1.
Input: nums = [34,23,1,24,75,33,54,8], k = 60
Output: 58
Объяснение: Мы можем использовать 34 и 24, которые в сумме дают 58, что меньше 60.

Пример 2.
Input: nums = [10,20,30], k = 15
Output: -1
Объяснение: В массиве нет пары чисел, которые дали бы сумму, меньшую 15.

def two_sum_less(arr, target):
    arr.sort()
    
    nearest_sum = -1
    
    left = 0
    right = len(arr) - 1

    while left < right:
        if arr[left] + arr[right] < target:
            nearest_sum = max(nearest_sum, arr[left] + arr[right])
            left += 1
        else:
            right -= 1
    return nearest_sum

3. Расходимся в противоположные стороны

Дан массив целых чисел, отсортированный по возрастанию. Необходимо вернуть массив квадратов этих чисел, отсортированный так же по возрастанию.

Получим два отсортированных подмассива:

1. Первый подмассив из бывших отрицательных чисел убывает
2. Второй подмассив из бывших положительных чисел растет

def sorted_squares(arr):
    # Устанавливаем индексы left и right на начало подмассивов.
    #
    # left будет указывать на последний отрицательный элемент, либо будет равен -1,
    # если все элементы в массиве положительные.
    left = -1
    for i, val in enumerate(arr):
        if val > 0:
            left = i - 1
            break
        else:
            left = len(arr) - 1
            
    # right будет идти сразу за left, но если в массиве нет положительных элементов,
    # то right будет равен длине массива.
    right = left + 1
    
    # Возводим в квадрат.
    arr = [n * n for n in arr]
    
    # Сливаем два отсортированных массива в один, как делали раньше.
    result = []
    while left >= 0 or right < len(arr):
        if left < 0:
            result.append(arr[right])
            right += 1
        elif right >= len(arr):
            result.append(arr[left])
            left -= 1
        elif arr[left] <= arr[right]:
            result.append(arr[left])
            left -= 1
        else: # arr[left] > arr[right]
            result.append(arr[right])
            right += 1
    return result

def sorted_squares(arr):
    # Заранее создаем пустой массив нужной длины,
    # ведь мы будем наполнять его с конца.
    result = [None] * len(arr)
    
    left = 
    right = len(arr) - 1
    i = right
    
    while i >= 0:
        if abs(arr[left]) >= abs(arr[right]):
            result[i] = arr[left] * arr[left]
            left += 1
        else:
            result[i] = arr[right] * arr[right]
            right -= 1
        i -= 1
        
    return result

Кстати, мы регулярно запускаем курс по подготовке к алгоритмическим собеседованиям

На курсе мы:

• прорабатываем всю теорию, которая нужна для успешного прохождения алгосекции
• учимся понимать суть и идею каждого задания без заучивания схемы решения
• решаем все задачки, которые могут встретиться на алгоритмическом собеседовании: простые и уровня hard+
• разбираем задания, которые встречались на реальных собеседованиях в OZON, Яндекс, ВК, Тинькофф, СБЕР и Авито + рассказываем особенности прохождения собеседований в эти компании и типичные темы, которые они спрашивают
• проводим mock-собеседования и code-review, чтобы избавиться от боязни интервьюера и научиться читать код своих коллег на работе

Подробнее о курсе