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

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

Пример 1:
Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: результаты [4,2,3,1], [2,4,1,3] и [4,2,1,3] также были бы приняты.

Пример 2:
Input: nums = [0]
Output: [0]

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

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

Решение
Используем метод двух указателей, движущихся в одном направлении (в этом случае сохранится относительный порядок чётных чисел в массиве):
left - индекс, указывающий, куда нужно записать следующее чётное число;
right - указатель, который проходит по массиву и последовательно проверяет каждый эл-т на чётность.
Вначале оба указателя указывают на первый эл-т.

Проходим указателем right по массиву nums:
- если число чётное: меняем его местами с числом на позиции left;
- сдвигаем указатель left вправо.

В конце возвращаем изменённый массив nums.

Сложность
O(n) - по времени (проходим по массиву длиной n)
O(1) - по памяти (храним две переменные, меняем эл-ты in-place)

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

for right in range(len(nums)):
if nums[right] % 2 == 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1

return nums

@algoses