Rotating a Matrix (Posted on April 20th, 2013)
From time to time when I'm bored I'll go through seemingly simple programming/interview challenges. One that I found interesting was the following:
Rotate an NxN matrix 90 degrees in the clockwise direction.
Sometimes the question also has a "bonus" challenge of rotating the matrix in memory. So basically without creating a new array or matrix. I'm not really a fan of this addition since it takes the naive approach off the board. Granted the naive approach is really dirty compared to what it actually takes to solve this problem. In fact if you know the trick the problem can be solved in a few lines of code.
The trick or algorithm for the problem is to first transpose the matrix and then to reverse each row in the matrix. You'll find this without too much searching. In fact there's a whole Wikipedia article on how to transpose a matrix in memory. If you're interested here's the "standard" solution:
matrix =[[1,2,3,4,5], [6,7,8,9,10], [11,12,13,14,15], [16,17,18,19,20], [21,22,23,24,25]] matrix_length = len(matrix) #Transpose matrix for n in range(0, matrix_length - 1): for m in range(n+1, matrix_length): matrix[n][m], matrix[m][n] = matrix[m][n], matrix[n][m] #Print out each row reversed for row in matrix: print(row[::-1])
However, there's a slightly cooler solution that will work in Python and possibly some other languages. I can't take credit for this solution as I learned it from this Stack Overflow answer, but I wanted to share it.
matrix =[[1,2,3,4,5], [6,7,8,9,10], [11,12,13,14,15], [16,17,18,19,20], [21,22,23,24,25]] #Rotate 90 degrees clockwise print(list(zip(*matrix[::-1]))) #Rotate 90 degrees counterclockwise print(list(zip(*matrix)))[::-1]
The "*" operator before the matrix variable is how you can unpack something in Python. For instance I could do this instead:
zip(*matrix) #or zip(matrix, matrix, matrix, matrix, matrix)
Zip is a super useful function that allows us to loop through multiple elements at the same time. So zip is grabbing the first item in each row and putting that into the first row which is exactly what our transpose is doing. While this solution isn't done in memory it satisfies the original problem in a pretty neat way. In any case code golfing is super fun.
Tags: Python, Challenges
My name is Max Burstein and I am a graduate of the University of Central Florida and creator of Problem of the Day and Live Dota. I enjoy developing large, scalable web applications and I seek to change the world.