Привет. Https://Leetcode.Com/Discuss/Interview-Question/309656/Google-Reorder-Array-According-To-The-Given-Indexes/ Возникла в коде аналогичная задача, единственный важный нюанс менять массив

индексов нельзя (ну и массив значений не числа)
И в общем я попробовал решить ее в таких условиях и у меня не получилось (в итоге я забил и сделал за O(n)).
Но осталось любопытно это вообще возможно? Если нет то как доказать что невозможно.

Вы имеете в виду O(n) по времени или по памяти?

Прочитайте пожалуйста описание по ссылке. Хочется решить за линию по времени и константу по памяти, с озвученным условием

Вы сейчас отредактировали своё сообщение, и исправили "за O(n)" на "за O(n) по памяти". Об этом и был вопрос)

Ну да, я подумал мб это было непонятно, просто все решения за линию по времени, поэтому мне казалось что подразумевается по памяти

Думаю, за единицу по памяти тут не получится, потому что запрос вида «Поставь число, которое в начале было на позиции a[x1], на позицию x2» Вынуждает нас хранить где-то изначальный элемент a[x2] до тех пор, пока мы не встретим запрос «Поставь число, которое в начале было на позиции a[x2], на позицию a[x3]» Если мы хотим O(1) памяти, мы должны выполнять запрос с присваиванием a[x2] сразу после запоминания a[x2]. Но найти такой запрос можно только с помощью обратных индексов или перебора за квадрат, что в наши ограничения не укладывается. В оригинале же эта проблема решается только тем, что нужные нам O(n) памяти уже выделены.

Не, это как раз легко, мы в рамках циклической перестановки можем расставить все правильно, проблема с тем как перейти к следующей такой перестановке

Ну я к такому же выводу пришел, но хотелось бы более формально

Ну, для алгоритма поиска всех перестановок нам нужен массив used, это уже O(n) памяти. Даже чтобы перейти к следующей перестановке, очевидно, он тоже нужен