Два елементи можна поміняти місцями тоді й лише тоді, коли їхні значення мають однакову остачу від ділення на , де остача береться з \{0, 1, 2\}. Розіб'ємо позиції на три класи за значенням a_i \bmod 3. Значення ніколи не змінюються, а операція зачіпає дві позиції одного класу, тож кожен клас зберігає на своїх позиціях свою мультимножину значень.
Навпаки, будь-які два елементи одного класу можна поміняти місцями безпосередньо, а кожна перестановка є добутком транспозицій. Отже, значення класу можна розставити на позиціях цього класу в будь-якому порядку незалежно від інших класів. Досяжні масиви — це рівно ті масиви, у яких кожен клас містить свої значення в якомусь порядку.
Нехай — масив, у якому кожен клас отримує свої значення, відсортовані за зростанням і розставлені на його позиціях зліва направо. Це лексикографічно найменший досяжний масив: візьмемо будь-який інший досяжний масив і першу позицію , де b_i \ne c_i, і нехай — клас позиції . Позиції класу ліворуч від містять у і в однакові значення, тож c_i — одне з решти значень класу , а b_i — найменше з них. Отже, b_i < c_i.
Тому для кожного класу збираємо його позиції та значення, сортуємо значення й записуємо їх назад по порядку. Єдина пастка — остача від'ємного числа: у C++ і Java -1 \,\%\, 3 = -1, хоча 2 - (-1) = 3 ділиться на , тож слід використовувати ((a_i \,\%\, 3) + 3) \,\%\, 3.
Складність — O(n \log n) на один тестовий випадок.