Задача с собеседования в TCS

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

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

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

Ограничения:
1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁵

НАШ ЧАТ АЛГОРИТМИСТОВ

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

max_reach - самый дальний индекс, до которого можем допрыгнуть; инициализируем, как 0, так как начинаем с индекса 0.

Проходим по массиву nums (i - индекс, на который хотим прыгнуть на текущей итерации):
- Если i больше значения max_reach: мы застряли и не можем достичь проверяемой позиции -> достичь конца массива невозможно, возвращаем False;
- Иначе, если можем достичь индекса i: из текущей позиции можно прыгнуть на nums[i] шагов, то есть возможно достичь индекса (i + nums[i]). Сравниваем прошлый максимум доступной нам дальности с новым, обновляя max_reach.

Если удалось пройти от начала до конца массива, возвращаем True.

Сложность
O(n) - по времени (один раз проходим по массиву длиной n)
O(1) - по памяти (храним только одну переменную max_reach)

Код
class Solution:
def canJump(self, nums: List[int]) -> bool:
max_reach = 0

for i in range(len(nums)):
if i > max_reach:
return False
max_reach = max(max_reach, i + nums[i])

return True

@algoses