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

Дан массив nums, состоящий из n объектов, окрашенных в красный, белый и синий цвета. Отсортируйте их in-place так, чтобы объекты одного цвета оказались соседними, следуя порядку: красные, белые, синие.
Будем использовать целые числа 0, 1 и 2 для обозначения красного, белого и синего, соответственно.
Решите задачу без использования встроенной функции сортировки.

Follow up: можете ли вы реализовать однопроходный алгоритм, использующий только константную дополнительную память?

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

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

Ограничения:
n == nums.length
1 <= n <= 300
nums[i] is either 0, 1, or 2.

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

Сборник алгоритмический задач с собесов

Решение
Базовое решение: двухпроходный алгоритм с сортировкой подсчётом. При первом проходе - подсчитываем кол-во 0, 1 и 2. При втором - перезаписываем массив, помещая сначала все 0, затем все 1 и, наконец, все 2.
Сложность такого алгоритма: O(n) - по времени (проходим по массиву два раза) и O(1) - по памяти (храним только три переменные, перезаписываем массив in-place).


Однако, предлагаю реализовать решение с использованием однопроходного алгоритма (follow-up). Для этой задачи подойдёт алгоритм "Национальный флаг Нидерландов", использующийся для сортировки массива с тремя различными значениями за один проход.

Основная идея в разделении массива на три части (по типу цветовых границ на флаге) и использовании трёх указателей:
low (сначала равен нулю) - отслеживает границу, где должны заканчиваться 0;
mid (сначала равен нулю) - проходит по массиву слева направо;
high (сначала равен len(nums) - 1) - отслеживает границу, где должны начинаться 2.

Идём по массиву указателем mid, пока mid <=high:
Если текущий элемент равен 0: меняем его местами с элементом под индексом low и увеличиваем значения обоих указателей;
Если текущий элемент равен 1: оставляем его на месте и сдвигаем указатель mid вперёд;
Иначе, если текущий элемент равен 2: меняем его местами с элементом под индексом high и уменьшаем значение указателя high. Указатель mid не сдвигается, так как нужно проверить эл-т, который пришёл из правой части.

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

Код
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
low, mid = 0, 0
high = len(nums) - 1

while mid <= high:
if nums[mid] == 0:
nums[mid], nums[low] = nums[low], nums[mid]
mid += 1
low += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1

@algoses