Needed help !!!!!!How to sort 2 d vector if given vector is rowwise sorted without using extra space in c++

Question

https://code.sololearn.com/c286kYH4uPCB/?ref=app
I tried like this but getting error
Output should be{{1,2,3}{3,5,6}{6,9,9}}
No Extra space means space complexity must be O(1)

Answer 1

Ipang i edited the question ,you can see it

Answer 2

Srishti Jaiswal,
Thanks for updating the post with extra details, looks more precise now.

I personally think this one is pretty tough, the O(1) goal especially.

Let's hear what community says ...

Answer 3

Given this data from your code, what output did you expect?

{ { 1, 3, 5 }, { 2, 6, 9 }, { 3, 6, 9 } }

And what was that "extra space" about? what spaces?

Answer 4

I would do something like the following:
1. sort each row in place - then the first element of each row is the smallest one locally
2. swap rows with columns: swap a[i][j] with a[j][i]
3. sort each row again - then the first element of the first row is the smallest element overall
4. swap rows with columns again
5. repeat
You should figure out how many repeats you need to do but in theory at some point you should get all the elements sorted without using any extra space.
The time complexity would not be ideal but you cannot have both efficient memory usage and efficient CPU usage.