Jump Game

Задача

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

Нужно вернуть true, если мы можем достичь последний индекс, иначе false.

Пример 1:

nums = [2,3,1,1,4]
Результат: true
Прыжок на 1 шаг с индекса 0 до 1, затем прыжок на 3 шага до последнего индекса.

Пример 2:

nums = [3,2,1,0,4]
Результат: false
Вы всегда окажетесь на индексе 3, независимо от выбора. Максимальная длина прыжка на этом индексе — 0, что делает невозможным достижение последнего индекса.

Ссылка на leetcode: https://leetcode.com/problems/jump-game

Решение

Удобней решать задачу с конца и идти к началу.

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

Из ячейки с индексом i = 3 можно прыгнуть максимум на одну ячейку, то есть достичь ячейку с индексом 4. Таким образом, если мы окажемся в ячейке с индексом 3, мы сможем добраться до конца массива.
Поэтому изменим значение переменной goal на 3.

Переместим индекс i на одну ячейку влево.

Из ячейки с индексом i = 2 мы можем прыгнуть максимум на одну ячейку, то есть достичь ячейку с индексом 3. А на предыдущем шаге мы уже выяснили, что, достигнув ячейки с индексом 3, можно добраться до конца массива. Поэтому обновим goal = 2.

Переместим индекс i на одну ячейку влево.

Из ячейки с индексом i = 1 мы можем прыгнуть на 1, 2 или 3 ячейки, то есть достичь любую ячейку с индексом, не превышающим i + nums[i]. Очевидно, что в этом случае мы сможем достичь ячейку, которая в данный момент обозначена как goal (goal = 2).

Теперь мы можем сформулировать ключевое условие для обновления переменной goal: если i + nums[i] >= goal, то мы можем присвоить goal = i. Выражение i + nums[i] обозначает максимальный индекс ячейки, которую можно достичь из позиции i. Если из этой позиции можно допрыгнуть до текущего значения goal, это означает, что начиная с ячейки с индексом i, мы можем добраться до конца массива.

Последние пару итераций алгоритма:

из ячейки с индеком i = 0 мы можем допрыгнуть до ячеек и индексами 1 и 2. Очевидно, что мы сможем допрыгнуть до ячейки goal = 1.

Финальное состояние:

Если goal = 0, это означает, что существует способ добраться до конца массива, начиная с его начала.

Реализация алгоритма тривиальна: проходим по массиву с конца к началу, начиная с предпоследнего элемента. На каждом шаге проверяем: если i + nums[i] >= goal, то обновляем goal = i.

Если в конце выполнения goal == 0, значит, существует способ допрыгать до конца массива.

Time Complexity = O(N)
Space Complexity = O(1)

Реализация

public boolean canJump(int[] nums) {
    int goal = nums.length - 1;
    for (int i = nums.length - 2; i >= 0; i--) {
        if (i + nums[i] >= goal) {
            goal = i;
        }
    }
    return goal == 0;
}