Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Rotate a 2D array in-place without using a new array - best C++ solution?

One of my students asked me this kind of homework with C++ arrays. It seemed quite interesting for me, so, though I have solved this problem, I wanted to share my solution with you and know another variants and opinions. The problem is following:

Problem It is given a 2D dynamic quadratic matrix (array) A(nxn). It is required to rotate the array by 90 degree anticlockwise, that is to say, after rotation A[1,1] field should contain the value of A[1,n] and A[1,n] field should contain the value of A[n,n]. And also it is required that while solving this problem you should not use any other array.

My solution I have told to the student to do the following (will represent steps schematically):
I have suggested to define a class which, as its member, will have the 2D array. And to define a operation which will return reference on A[j,n+1-i] element when the user will request A[i,j] one. In two words I have suggested to create a wrapper for the array, and manipulate by array through the wrapper.

like image 852
Narek Avatar asked Jun 29 '10 12:06

Narek


1 Answers

Wikipedia has an article on in-place matrix transposition.

Consider:

a b c
e f g
x y z

transpose:
a e x
b f y
c g z

rotated 90 deg CCW:
c g z
b f y
a e x

So after you have the transpose, reverse the rows, which you can do in-place easily.

like image 111
IVlad Avatar answered Sep 21 '22 10:09

IVlad