## Matrix Rotation

### June 6, 2017

We have a two-part exercise today, based on a Microsoft interview question.

First, write a program to rotate an *m* × *n* matrix 90° to the right, as shown below; your solution should touch each matrix element only once:

a b c d e f m j g d a A = g h i rot(A) = n k h e b j k l o l i f c m n o

Second, write a program to rotate a square matrix with *n* rows and columns *in-place*. where the source and target matrices are the same matrix and there is no intermediate matrix (be sure your solution works for both even and odd *n*):

a b c d e u p k f a f g h i j v q l g b B = k l m n o rot(B) = w r m h c p q r s t x s n i d u v w x y y t o j e

Your task is to write the two programs that rotate matrices. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

The first part of the exercise in Python

Both parts of the exercise in Julia. Just a single generic method covering all possibilities.

function rotate{T <: Any}(X::Matrix{T})

n = size(X, 1)

n1 = n + 1

Y = X'

for i = 1:div(n, 2)

j = n1 – i

Y[:,i], Y[:,j] = Y[:,j], Y[:,i]

end

return Y

end

The second part in Python. The rotation is done by swapping two matrix elements at the time.

A better version of the second part. This version sets the matrix elements only once.

Klong version

Python 3.6.

rot() is basically the same as Paul’s.

rot_in_place() moves four corresponding elements at a time. ‘i’ can be thought of as the layer or ring, 0 being the outermost ring.

‘i’, ‘ir’, ‘j’, and ‘jr’ are the row or column indices of the elements being moved.

rot = lambda m:[*zip(*m[::-1])]

def rot_in_place(a):

n = len(a)

for i in range((n+1) // 2):

ir = -i-1

for j in range(i, n-i-1):

jr = -j-1

(a[i][j], a[j][ir],

a[jr][i],a[ir][jr]) = (a[jr][i], a[i][j],

a[ir][jr],a[j][ir])