Jump Game: можно ли допрыгать до конца массива за O(n)

Коротко

• Главная идея: достижимые индексы всегда образуют непрерывный отрезок от нуля, поэтому вместо всего множества хватает одного числа — самой дальней достижимой позиции.
• «Жадность» здесь не значит «прыгай как можно дальше». Такая стратегия ошибается. Алгоритм вообще не выбирает прыжки, он только двигает границу.
• Типовое продолжение — Jump Game II с минимумом прыжков. Решается обходом в ширину по отрезкам, тоже за $O(n)$.

Условие

Дан массив неотрицательных чисел nums. Вы стоите на индексе 0. Значение nums[i] — максимальная длина прыжка из позиции i: можно прыгнуть на любое расстояние от 1 до nums[i]. Нужно понять, можно ли добраться до последнего индекса.

nums = [2, 3, 1, 1, 4]  →  true   (0 → 1 → 4)
nums = [3, 2, 1, 0, 4]  →  false  (все пути упираются в ноль на индексе 3)

Это задача 55 на LeetCode. У нас на сайте она называется «Прыжки по массиву», там можно сразу запустить решение. Длина массива в ней до $10^4$.

Запомните слово «максимальная». Вся красота решения держится именно на нём, и позже мы к этому вернёмся.

Перебор: с чего начать рассуждение

Индексы можно считать вершинами графа, а возможные прыжки — рёбрами, идущими только вперёд. Вопрос звучит так: есть ли путь из вершины 0 в вершину n - 1? Самый прямой ответ — попробовать все пути.

def can_jump_brute(nums: list[int]) -> bool:
    last = len(nums) - 1

    def go(i: int) -> bool:
        if i == last:
            return True
        for step in range(1, nums[i] + 1):
            if i + step <= last and go(i + step):
                return True
        return False

    return go(0)

Код верный, но число путей растёт экспоненциально. На массиве [k, k-1, ..., 1, 0, 0] все пути упираются в ноль, и функция обходит их все: go вызывается ровно $2^k$ раз. При k = 20 это уже больше миллиона вызовов на массив из 22 элементов.

При этом перебор решает одни и те же подзадачи снова и снова. Ответ для индекса i не зависит от того, как мы туда попали. Это прямой намёк на динамическое программирование.

Динамика за O(n²)

Можно просто добавить мемоизацию в перебор: подзадач станет $n$, каждая потребует не больше $n$ проверок. Но на Python при стандартном лимите это упадёт: на [1] * 10000 глубина рекурсии равна длине массива, и мы получим RecursionError. Поэтому сразу напишем динамику снизу вверх.

Пусть reachable[i] означает «до индекса i можно добраться». Индекс достижим, если найдётся достижимый индекс левее, с которого до него хватает длины прыжка:

def can_jump_dp(nums: list[int]) -> bool:
    n = len(nums)
    reachable = [False] * n
    reachable[0] = True

    for i in range(1, n):
        for j in range(i):
            if reachable[j] and j + nums[j] >= i:
                reachable[i] = True
                break

    return reachable[-1]

Это честное решение, но два вложенных цикла дают $O(n^2)$. На [1] * 10000 внутренний цикл каждый раз доходит почти до i, потому что подходит только соседний слева индекс. Выходит 49 995 000 проверок. В локальном прогоне на CPython 3.9 это заняло около 2,5 секунды. Решение из следующего раздела на том же входе уложилось примерно в 1 мс.

От динамики к жадности: убираем внутренний цикл

Посмотрите внимательно, что делает внутренний цикл. Он отвечает на вопрос: есть ли среди достижимых j левее i такой, что j + nums[j] >= i?

Но «есть хотя бы один элемент не меньше i» — то же самое, что «максимум не меньше i»:

Максимум на префиксе не нужно пересчитывать заново, его легко поддерживать одной переменной. Массив reachable тоже становится лишним: чтобы продолжить, нам нужно только знать, что текущий индекс достижим, а это и есть условие i <= reach.

def can_jump(nums: list[int]) -> bool:
    reach = 0  # самый дальний индекс, до которого точно можно добраться

    for i, jump in enumerate(nums):
        if i > reach:
            return False  # сюда уже не добраться, а значит и дальше тоже
        reach = max(reach, i + jump)

    return True

Вот и всё решение. Заметьте: мы не придумывали жадность из воздуха, а получили её механическим упрощением динамики. Такой путь намного проще воспроизвести на собеседовании, чем пытаться сразу «увидеть» ответ.

Почему это корректно

Вывод выше уже почти доказательство, но есть одна тонкость: досрочный return False опирается на то, что за недостижимым индексом ничего достижимого нет. Откуда мы это знаем? Здесь и нужны два факта.

Факт 1: достижимые индексы образуют непрерывный отрезок. Пусть индекс k достижим и j < k. Возьмём путь от 0 до k. Индексы на нём только растут, поэтому либо j лежит на пути, либо какой-то прыжок p → q перелетает через него: p < j < q. Длина этого прыжка не больше nums[p], а расстояние j - p ещё меньше. Значит, из p можно прыгнуть прямо в j. Выходит, что вместе с k достижимы и все индексы левее него.

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

Факт 2: индекс i достижим тогда и только тогда, когда i <= reach. Докажем в обе стороны, считая reach максимумом j + nums[j] по всем j < i (при i = 0 индекс достижим по условию).

• Если i <= reach, то есть такой j < i, что j + nums[j] >= i. Этот j достижим, ведь алгоритм до него дошёл. Значит, из него можно прыгнуть в i.
• Если i достижим, то последний прыжок на пути к нему сделан из какого-то j < i, и j + nums[j] >= i. Значит, reach >= i.

Теперь досрочный выход обоснован. Если i > reach, то по факту 2 индекс i недостижим, а по факту 1 недостижимы и все индексы правее него, включая последний.

Что здесь на самом деле жадного

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

В Jump Game мы не выбираем конкретный путь. Мы описываем сразу всё множество достижимых позиций, и благодаря факту 1 оно сжимается до одного числа. Жадная часть только в том, что мы всегда запоминаем лучшую границу и никогда не откатываемся назад.

Когда это перестаёт работать

Поменяйте одно слово в условии: пусть из i можно прыгнуть ровно на nums[i]. Факт 1 сразу разваливается. На [2, 9, 0, 9] из индекса 0 попадаем только на индекс 2, а индекс 1 перелетаем. На индексе 2 стоит ноль, так что последний индекс недостижим. Но can_jump вернёт True: она учтёт девятку на индексе 1, хотя туда никто не приходил.

Отсюда полезная проверка для любой похожей задачи: образуют ли допустимые состояния отрезок? Если да, скорее всего, хватит границы. Если нет, придётся честно обходить состояния.

Разбор на примере

Первый массив, [2, 3, 1, 1, 4]:

Цикл дошёл до конца, ответ True. Значение reach = 8 выходит за пределы массива, и это нормально: граница означает «дальше точно можно», а не конкретный индекс. Если хотите, добавьте ранний выход if reach >= len(nums) - 1: return True, но на асимптотику это не влияет.

Второй массив, [3, 2, 1, 0, 4]:

На индексе 4 условие сработало, ответ False. Обратите внимание: каждый индекс от 0 до 3 упирается ровно в тройку. Граница перестала расти, и дальше ей взяться неоткуда.

Вариант с обратным проходом

Иногда ту же идею записывают с конца: держим самую левую позицию goal, из которой уже точно можно дойти до финиша.

def can_jump_backward(nums: list[int]) -> bool:
    goal = len(nums) - 1

    for i in range(len(nums) - 2, -1, -1):
        if i + nums[i] >= goal:
            goal = i

    return goal == 0

Почему достаточно смотреть только на goal, а не на все хорошие позиции правее? Все они лежат не левее goal. Если из i можно допрыгнуть до какой-то из них, то по пути лежит и goal, а значит, можно прыгнуть и туда.

Сложность та же: $O(n)$ по времени и $O(1)$ по памяти. Выбирайте вариант, который вам проще объяснить. Прямой проход обычно удобнее, потому что от него легко перейти к Jump Game II.

Сложность

Время: $O(n)$. Один проход по массиву и константная работа на каждом индексе.

Память: $O(1)$. Только одна переменная reach.

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

Типичные ошибки

Всегда прыгать на максимум. Главная ловушка задачи. На [2, 5, 0, 0] такой код прыгает с нуля на индекс 2 и застревает на нуле. А правильный путь есть: 0 → 1 → 3. Короткий прыжок на пятёрку оказался лучше длинного прыжка в тупик.

Обновлять reach до проверки. Порядок важен. Если поменять строки местами, на [0, 1] на индексе 1 сначала получится reach = 2, и условие 1 > 2 не сработает. Функция вернёт True, хотя с нулевого индекса выбраться нельзя. Мы учли прыжок из позиции, куда не попали.

Считать ноль в начале проигрышем. Проверка if nums[0] == 0: return False ломает случай [0]: мы уже стоим на последнем индексе, и правильный ответ — True.

Считать любой ноль тупиком. На [2, 0, 1] ноль просто перепрыгивается. Ноль опасен лишь тогда, когда граница reach останавливается ровно на нём.

Сдать рекурсию с мемоизацией как итоговое решение. Даже если она пройдёт по времени, в Python упрётся в лимит глубины рекурсии, а поднимать его через sys.setrecursionlimit — так себе аргумент на собеседовании.

Назвать алгоритм и не объяснить, почему он работает. Код здесь короткий, и его многие знают наизусть. Поэтому интервьюер вполне может спросить, почему одной переменной достаточно. Ответьте фактом про непрерывный отрезок.

Jump Game II: минимум прыжков

Это задача 45 на LeetCode и типовое продолжение. Теперь гарантируется, что до конца добраться можно, а нужно найти минимальное число прыжков.

nums = [2, 3, 1, 1, 4]  →  2   (0 → 1 → 4)

Сначала снова динамика

dp[j] — минимальное число прыжков до индекса j. Из каждого i обновляем всё, что можно достать:

def jump_dp(nums: list[int]) -> int:
    n = len(nums)
    dp = [float('inf')] * n
    dp[0] = 0

    for i in range(n):
        for j in range(i + 1, min(i + nums[i], n - 1) + 1):
            dp[j] = min(dp[j], dp[i] + 1)

    return dp[-1]

В худшем случае это снова $O(n^2)$: на массиве из $10^4$ элементов, каждый из которых равен $10^4$, локальный прогон занял почти 6 секунд.

Жадность «прыгай дальше» снова не работает

На [2, 3, 1, 1, 4] прыжок на максимум даёт путь 0 → 2 → 3 → 4, то есть 3 прыжка. Оптимальный путь 0 → 1 → 4 начинается с короткого прыжка, зато из индекса 1 можно улететь дальше.

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

Обход в ширину по отрезкам

Разобьём индексы на уровни, как в обходе в ширину: уровень $k$ — это индексы, до которых минимум $k$ прыжков.

Рассуждение из факта 1 работает и здесь. Если до k можно добраться за $d$ прыжков, то до любого индекса левее тоже можно не больше чем за $d$: тот же путь, только прыжок через j заканчиваем в j. Значит, минимальное число прыжков не убывает слева направо, и каждый уровень — непрерывный отрезок.

Настоящая очередь не нужна. Идём слева направо и считаем, куда можно долететь из текущего уровня. Когда текущий уровень заканчивается, накопленный максимум становится границей следующего.

def jump(nums: list[int]) -> int:
    jumps = 0
    level_end = 0  # правая граница текущего уровня
    farthest = 0  # куда можно долететь с индексов, просмотренных до сих пор

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == level_end:
            jumps += 1
            level_end = farthest

    return jumps

Разбор на [2, 3, 1, 1, 4]:

Ответ — 2 прыжка. Время $O(n)$, память $O(1)$.

Почему цикл идёт до n - 1, а не до n

Здесь легко ошибиться. Последний индекс нельзя обрабатывать: на нём не надо никуда прыгать. Если пройти по всему массиву, то, когда граница уровня совпадёт с последним индексом, счётчик увеличится лишний раз. На [2, 3, 1, 1, 4] получится 3 вместо 2, а на [0] — 1 вместо 0.

Если достижимость не гарантирована

Интервьюер может убрать гарантию и попросить вернуть -1. Проверка простая: если текущий уровень закончился, а граница не сдвинулась, идти дальше некуда.

def jump_or_fail(nums: list[int]) -> int:
    jumps = 0
    level_end = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == level_end:
            if farthest == i:
                return -1
            jumps += 1
            level_end = farthest

    return jumps

Если нужен сам путь

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

def jump_path(nums: list[int]) -> list[int]:
    path = [0]
    level_end = 0
    farthest = 0
    best = 0

    for i in range(len(nums) - 1):
        if i + nums[i] > farthest:
            farthest = i + nums[i]
            best = i
        if i == level_end:
            if i > 0:
                path.append(best)
            level_end = farthest

    if len(nums) > 1:
        path.append(len(nums) - 1)
    return path


print(jump_path([2, 3, 1, 1, 4]))  # [0, 1, 4]

Задачи, которые сводятся к Jump Game II

Шаблон с границей уровня часто прячется в задачах о покрытии отрезка. Пример — LeetCode 1326, Minimum Number of Taps: сад занимает отрезок [0, n], кран в точке i поливает [i - ranges[i], i + ranges[i]], нужно открыть как можно меньше кранов.

Для каждой левой точки запоминаем, как далеко вправо от неё можно достать. Получаем массив прыжков, и дальше это уже знакомая задача:

def min_taps(n: int, ranges: list[int]) -> int:
    jumps = [0] * (n + 1)

    for i, r in enumerate(ranges):
        left = max(0, i - r)
        right = min(n, i + r)
        jumps[left] = max(jumps[left], right - left)

    return jump_or_fail(jumps)


print(min_taps(5, [3, 4, 1, 1, 0, 0]))  # 1
print(min_taps(3, [0, 0, 0, 0]))  # -1

Video Stitching (LeetCode 1024) устроена так же, только вместо кранов отрезки видео. А родственную работу с отрезками и сдвигом правой границы стоит потренировать на задачах с интервалами.

Остальная серия Jump Game

Названия у задач похожие, а подходы разные. Граница работает только там, где достижимые состояния образуют отрезок:

Как только в задаче появляются очки, запреты или прыжки строго фиксированной длины, множество достижимых состояний перестаёт описываться одним числом, а значит, простой границы уже мало.

Как это звучит на собеседовании

Jump Game есть в подборках Blind 75 и NeetCode 150, а Jump Game II — в NeetCode 150, так что обе задачи стоит держать в голове. Надёжных данных о том, как часто их дают в конкретных компаниях, у нас нет, поэтому цифр обещать не будем.

Хороший ответ занимает несколько минут и строится так:

1. Уточнить условие: можно прыгать на любую длину до nums[i] или только ровно на неё? Могут ли быть отрицательные значения?
2. Коротко назвать динамику за $O(n^2)$ и показать, как внутренний цикл сводится к максимуму на префиксе.
3. Написать жадное решение и проговорить, почему достижимые индексы образуют отрезок.
4. Сразу прогнать крайние случаи: [0], [0, 1], [2, 0, 1], [2, 5, 0, 0].
5. Быть готовым к Jump Game II и вопросу про -1.

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

Что запомнить

• Jump Game решается одной переменной reach: граница самой дальней достижимой позиции.
• Жадное решение — это динамика с внутренним циклом, сжатым до максимума на префиксе.
• Корректность держится на том, что достижимые индексы образуют непрерывный отрезок. Это верно, потому что nums[i] — максимальная длина прыжка.
• Стратегия «всегда прыгай как можно дальше» неверна и в первой, и во второй задаче.
• Jump Game II — это BFS по отрезкам без очереди, а цикл в нём идёт до n - 1.

Теперь попробуйте сами: откройте «Прыжки по массиву» и напишите решение, не подглядывая.