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

Дан массив целых чисел nums, сдвиньте его вправо на k шагов, где k - неотрицательное число.

Follow up:
- Постарайтесь придумать, как можно больше решений. Существует, по крайней мере, три разных способа решения этой задачи;
- Можно ли решить задачу in-place, используя O(1) дополнительной памяти?

Пример 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
сдвиг на один шаг вправо: [7, 1, 2, 3, 4, 5, 6]
сдвиг на два шага вправо: [6, 7, 1, 2, 3, 4, 5]
сдвиг на три шага вправо: [5, 6, 7, 1, 2, 3, 4]

Пример 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
сдвиг на один шаг вправо: [99, -1, -100, 3]
сдвиг на два шага вправо: [3, 99, -1, -100]

Ограничения:
1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
0 <= k <= 10⁵

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

Решение
Разберём один из способов решения этой задачи in-place - тройной разворот + метод двух указателей:

Заметим, что массив nums как бы состоит из двух частей. Первая часть - числа, которые стоят в начале, но должны переместиться в конец, вторая часть - числа, которые находятся в конце, но должны уйти в начало.
Алгоритм решения заключается в трёх разворотах.
Перед началом разворотов выполняем k = k % len(nums) - это гарантирует корректный ответ, если k больше или равен длине массива. Так как сдвиг на len(nums) шагов оставляет массив неизменным, отбрасываем "полные круги" и выполняем только эффективные сдвиги - остаток от деления k на длину массива.

Для визуализации рассмотрим работу алгоритма на примере 1:
1. Переворачиваем первую часть: от нулевого индекса до len(nums) - k - 1 (так как кол-во эл-тов, которые должны переместиться в начало, равно k).
[1,2,3,4,5,6,7] -> [4,3,2,1,5,6,7]
2. Переворачиваем вторую часть: от len(nums) - k до последнего эл-та массива.
[4,3,2,1,5,6,7] -> [4,3,2,1,7,6,5]
3. И теперь переворачиваем весь массив целиком, чтобы разместить числа в правильном порядке.
[4,3,2,1,7,6,5] -> [5,6,7,1,2,3,4]

Чтобы избежать дублирования кода, создаём отдельный метод для реверсирования эл-тов через метод двух указателей:
Пока l < r:
- меняем местами число под индексом l с числом под индексом r;
- двигаем левый указатель вправо, а правый указатель - влево.
Этот метод отрабатывает в каждом из трёх разворотов.

Делитесь вашим вариантом решения в комментариях!

Сложность
O(n) - время (где n - длина массива)
O(1) - память (изменяем исходный массив без создания дополнительной структуры данных (in-place), используем две переменные: l и r)

Код
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
k = k % len(nums)

self.reverse(nums, 0, len(nums) - k - 1)
self.reverse(nums, len(nums) - k, len(nums) - 1)
self.reverse(nums, 0, len(nums) - 1)

def reverse(self, nums: List[int], l: int, r: int) -> None:
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1

@algoses