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

Дан отсортированный в порядке возрастания массив nums, состоящий из уникальных целых чисел.
Известно, что диапазон [a, b] представляет собой множество всех целых чисел от a до b включительно.

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

Пример:
Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]

Чат алгоритмистов

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

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

Код

def summaryRanges(self, nums: List[int]) -> List[str]:
result = []
i = 0

while i < len(nums):
start = nums[i]
while i < len(nums) - 1 and nums[i] + 1 == nums[i + 1]:
i+= 1

if start != nums[i]:
result.append(str(start) + "->" + str(nums[i]))
else:
result.append(str(nums[i]))

i += 1

return result

@algoses