7439

21
+27  Q:

## How do you rotate a two dimensional array?

Inspired by Raymond Chen's post, say you have a 4x4 two dimensional array, write a function that rotates it 90 degrees. Raymond links to a solution in pseudo code, but I'd like to see some real world stuff.

[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]

Becomes:

[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]

Update: Nick's answer is the most straightforward, but is there a way to do it better than n^2? What if the matrix was 10000x10000?

+17  A:

Here it is in C#

int[,] array = new int[4,4] {
{ 1,2,3,4 },
{ 5,6,7,8 },
{ 9,0,1,2 },
{ 3,4,5,6 }
};

int[,] rotated = RotateMatrix(array, 4);

static int[,] RotateMatrix(int[,] matrix, int n) {
int[,] ret = new int[n, n];

for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
ret[i, j] = matrix[n - j - 1, i];
}
}

return ret;
}
Sure, but what about a solution using O(1) memory?
My solution below has O(1) memory and O(1) time performance: http://stackoverflow.com/questions/42519/how-do-you-rotate-a-two-dimensional-array/193942#193942
+1  A:

Here's my Ruby version (note the values aren't displayed the same, but it still rotates as described).

def rotate(matrix)
result = []
4.times { |x|
result[x] = []
4.times { |y|
result[x][y] = matrix[y][3 - x]
}
}

result
end

matrix = []
matrix[0] = [1,2,3,4]
matrix[1] = [5,6,7,8]
matrix[2] = [9,0,1,2]
matrix[3] = [3,4,5,6]

def print_matrix(matrix)
4.times { |y|
4.times { |x|
print "#{matrix[x][y]} "
}
puts ""
}
end

print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))

The output:

1 5 9 3
2 6 0 4
3 7 1 5
4 8 2 6

4 3 2 1
8 7 6 5
2 1 0 9
6 5 4 3
+1  A:

Nick's answer would work for an NxM array too with only a small modification (as opposed to an NxN).

string[,] orig = new string[n, m];
string[,] rot = new string[m, n];

...

for ( int i=0; i < n; i++ )
for ( int j=0; j < m; j++ )
rot[j, n - i - 1] = orig[i, j];

One way to think about this is that you have moved the center of the axis (0,0) from the top left corner to the top right corner. You're simply transposing from one to the other.

+7  A:

A couple of people have already put up examples which involve making a new array.

A few other things to consider:

(a) Instead of actually moving the data, simply traverse the "rotated" array differently.

(b) Doing the rotation in-place can be a little trickier. You'll need a bit of scratch place (probably roughly equal to one row or column in size). There's an ancient ACM paper about doing in-place transposes (http://doi.acm.org/10.1145/355719.355729), but their example code is nasty goto-laden FORTRAN.

http://doi.acm.org/10.1145/355611.355612 is another, supposedly superior, in-place transpose algorithm.

I agree with this. Have a method that determine the translation between the source data and the "rotated" data.
A:

Without using XOR, this can be done with two temporary scalar variables.

A:

Thanks for the answers thus far. Nick's answer was the first, most straightforward, but is there a way to do it better than n^2? What if the matrix was 10000x10000? Or higher?

edit: Kyle - you're right, I saw the nested for loops and assumed n^2... what I get for doing this after the work day :). My memory of matrix operations is foggy at best, but is there a multiplication to do this quickly?

+1  A:

@swilliams

Nick's answer isn't O(n^2), it's O(n), and I don't think you'll find any faster algorithm so long as there's no way to address rows or columns as groups. You have to pass through each element in order to swap them.

A:

Nick's answer is O(n.n) since the number of operations increases with the square of the rank of the matrix, so a rank 4 matrix (4x4) requires 16 operations and a rank 5 requires 25 operations.

I have an O(1) algorithm, but it's getting late here so I'll post the code tomorrow (ooohh, the suspense!)

Skizz

+16  A:

As I said in my previous post, here's some code in C# that implements an O(1) matrix rotation for any size matrix. For brevity and readability there's no error checking or range checking. The code:

static void Main (string [] args)
{
int [,]
//  create an arbitrary matrix
m = {{0, 1}, {2, 3}, {4, 5}};

Matrix
//  create wrappers for the data
m1 = new Matrix (m),
m2 = new Matrix (m),
m3 = new Matrix (m);

//  rotate the matricies in various ways - all are O(1)
m1.RotateClockwise90 ();
m2.Rotate180 ();
m3.RotateAnitclockwise90 ();

//  output the result of transforms
System.Diagnostics.Trace.WriteLine (m1.ToString ());
System.Diagnostics.Trace.WriteLine (m2.ToString ());
System.Diagnostics.Trace.WriteLine (m3.ToString ());
}

class Matrix
{
enum Rotation
{
None,
Clockwise90,
Clockwise180,
Clockwise270
}

public Matrix (int [,] matrix)
{
m_matrix = matrix;
m_rotation = Rotation.None;
}

//  the transformation routines
public void RotateClockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 1) & 3);
}

public void Rotate180 ()
{
m_rotation = (Rotation) (((int) m_rotation + 2) & 3);
}

public void RotateAnitclockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 3) & 3);
}

//  accessor property to make class look like a two dimensional array
public int this [int row, int column]
{
get
{
int
value = 0;

switch (m_rotation)
{
case Rotation.None:
value = m_matrix [row, column];
break;

case Rotation.Clockwise90:
value = m_matrix [m_matrix.GetUpperBound (0) - column, row];
break;

case Rotation.Clockwise180:
value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column];
break;

case Rotation.Clockwise270:
value = m_matrix [column, m_matrix.GetUpperBound (1) - row];
break;
}

return value;
}

set
{
switch (m_rotation)
{
case Rotation.None:
m_matrix [row, column] = value;
break;

case Rotation.Clockwise90:
m_matrix [m_matrix.GetUpperBound (0) - column, row] = value;
break;

case Rotation.Clockwise180:
m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value;
break;

case Rotation.Clockwise270:
m_matrix [column, m_matrix.GetUpperBound (1) - row] = value;
break;
}
}
}

//  creates a string with the matrix values
public override string ToString ()
{
int
num_rows = 0,
num_columns = 0;

switch (m_rotation)
{
case Rotation.None:
case Rotation.Clockwise180:
num_rows = m_matrix.GetUpperBound (0);
num_columns = m_matrix.GetUpperBound (1);
break;

case Rotation.Clockwise90:
case Rotation.Clockwise270:
num_rows = m_matrix.GetUpperBound (1);
num_columns = m_matrix.GetUpperBound (0);
break;
}

StringBuilder
output = new StringBuilder ();

output.Append ("{");

for (int row = 0 ; row <= num_rows ; ++row)
{
if (row != 0)
{
output.Append (", ");
}

output.Append ("{");

for (int column = 0 ; column <= num_columns ; ++column)
{
if (column != 0)
{
output.Append (", ");
}

output.Append (this [row, column].ToString ());
}

output.Append ("}");
}

output.Append ("}");

return output.ToString ();
}

int [,]
//  the original matrix
m_matrix;

Rotation
//  the current view of the matrix
m_rotation;
}

OK, I'll put my hand up, it doesn't actually do any modifications to the original array when rotating. But, in an OO system that doesn't matter as long as the object looks like it's been rotated to the clients of the class. At the moment, the Matrix class uses references to the original array data so changing any value of m1 will also change m2 and m3. A small change to the constructor to create a new array and copy the values to it will sort that out.

Skizz

Bravo! This is a very nice solution and I don't know why it isn't the accepted answer.
@martinatime: perhaps because it is 5 times as big
@Toad: Well, writing code is always a trade off between competing requirements: speed, size, cost, etc.
@skizz: true... another problem is the fact that the matrix is in fact not rotated, but is rotated 'just in time'. Which is great for accessing a few elements, but would be horrible if this matrix was used in calculations or image manipulations. So saying O(1) is not really fair.
+6  A:

Here is one that does the rotation in place instead of using a completely new array to hold the result. I've left off initialization of the array and printing it out. This only works for square arrays but they can be of any size. Memory overhead is equal to the size of one element of the array so you can do the rotation of as large an array as you want. (code is C++)

int a[4][4];
int n=4;
int tmp;
for (int i=0; i<n/2; i++){
for (int j=i; j<n-i-1; j++){
tmp=a[i][j];
a[i][j]=a[j][n-i-1];
a[j][n-i-1]=a[n-i-1][n-j-1];
a[n-i-1][n-j-1]=a[n-j-1][i];
a[n-j-1][i]=tmp;
}
}
I can see at least one bug. If you're going to post code, test it or at least say you haven't done so.
Where? Point it out and I'll fix it. I did test it and it worked fine on both odd and even sized arrays.
Just from looking: The second loop starts tests j < -i-1. It looks like j is always >= 0 and -i-1 is always negative, so the test never passes.
You're right. That's strange. I believe there is supposed to be an n in there that I left out when I posted it. Fixed it in the listing.
A:

@dagorym: Aw, man. I had been hanging onto this as a good "I'm bored, what can I ponder" puzzle. I came up with my in-place transposition code, but got here to find yours pretty much identical to mine...ah, well. Here it is in Ruby.

require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }

pp a

0.upto(n/2-1) do |i|
i.upto(n-i-2) do |j|
tmp             = a[i][j]
a[i][j]         = a[n-j-1][i]
a[n-j-1][i]     = a[n-i-1][n-j-1]
a[n-i-1][n-j-1] = a[j][n-i-1]
a[j][n-i-1]     = tmp
end
end

pp a
+11  A:

Whilst rotating the data in place might be necessary (perhaps to update the physically stored representation), it becomes simpler and possibly more performant to add a layer of indirection onto the array access, perhaps an interface:

{
int GetValue(int x, int y);
}

If your Matrix already implements this interface, then it can be rotated via a decorator class like this:

{

{
_baseMatrix = baseMatrix;
}

int GetValue(int x, int y)
{
// transpose x and y dimensions
return _baseMatrix(y, x);
}
}

Rotating +90/-90/180 degrees, flipping horizontally/vertically and scaling can all be achieved in this fashion as well.

Performance would need to be measured. However the O(n^2) operation has now been replaced with an O(1) call. It's a virtual method call which is slower than direct array access, so it depends upon how frequently the rotated array is used after rotation. If it's used once, then this approach would definitely win. If it's rotated then used in a long-running system for days, then in-place rotation might perform better. It also depends whether you can accept the up-front cost.

As with all performance issues, measure, measure, measure!

+1... I was going to add this O(1) solution.
+1... And if the matrix is really large and you only access a couple elements (sparse use) it's even more effective
What's happening under the covers here? Is it just aliasing or is the memory actually changing?
@jeffamaphone, the memory isn't changing. I guess you could think of it as aliasing, yes.
Will this work if I call GetValue(3,3). It will always return the original value and no transposition happens?
@Sesh, yes it still works because (A,B) is the same as (B,A) when A==B.
It seems a little unfair to call this an O(1) time solution. To solve the problem posed by the OP this will still take O(n^2) time. Not only that, it wouldn't solve the problem because it returns the *transpose*. The example given doesn't have the transpose as the solution.
@Goose Bumper -- the point is that the transposition isn't required to physically take place. Printing the matrix out takes O(n^2), but so does any exhaustive read operation, so you can't get away from that. The transposition was O(1) and each individual read is also O(1), so I stick by my assertion that this solution has constant time for rotation and subsequent reads. As I mention in the answer, this technique is not always the most appropriate.
No hire. This isn't O(1).
@Paul Betts, care to elaborate? I'm not trying do disagree, but I'm just curious about your reasoning.
@Paul Betts, please give more reasoning. I can't see how this isn't O(1). Anyway, who says I wanted to work for you? :)
Because to get the full contents of the new array, I must write the function:for(i=1 to n) { for(j=1 to n) { rotated.GetValue(i,j); } }You haven't magically made this constant time, you've just made someone else write the loop.
Now, if all you wanted was the first 3 *elements* of the matrix, this is a fine solution, but the problem is to retrieve a completely transformed matrix (i.e. assuming you need *all* the matrix elements). Calling this O(1) is the Credit Default Swap method of Algorithm Analysis - you haven't solved the problem, you've just pushed it to someone else :)
@Paul Betts: I get your point, but like I wrote above in the comments, even if you actually have the matrix transposed you still have to write the loop if you want to read the values out. So reading all values from a matrix is always O(N^2) regardless. The difference here is that if you transpose, rotate, scale, scale again, etc, then you still only take the O(N^2) hit once. Like I said, this isn't always the best solution, but in many cases it's appropriate and worthwhile. The OP seemed to be looking for a magic solution, and this is as close as you'll get.
As you say, if you only need 3 elements then this is faster, but I maintain that it's faster in most cases anyway. What good are the bytes laid out in memory if you don't read them? Whether it be random or sequential access, there's still a cost with reading them. This solution just avoids you having to read them all at the time you transfer them and then *again* later. You only do the read once. If you're hammering the matrix array for reads, then you might want a permanent version because the cost of dispatching virtual calls might start to outweigh the benefit of this approach.
Another consideration is whether the source matrix is immutable. This technique only works if the source doesn't change under you. There's another way of thinking about this approach. Rather than returning an array, we return the promise to provide the array when (and if) it's needed. It's similar to `IEnumerable`. 'Calculation' is lazy.
I like this answer, but I want to point something out. Printing out the decorated matrix (and doing other sequential reads in general) may be much slower than doing the same to a matrix that's been rotated in memory, and it's not just because of virtual method calls. For a big matrix, you're going to vastly increase the number of cache misses you get by reading "down" rather than "across".
@drew noakes, @paul betts : however you explain it, paul bett's point is valid. You didn't rotate the matrix but added layers of indirection which will do the transformation 'just in time'. Doing anything substantial with this matrix (matrix calculations or image manipulation) will seriously slow down because of it.
@Toad, yep. Like I said in the post and in the comments, it all depends. No one showed this solution here, and it's worth thinking about, even if you don't use it. In some cases, it'll be much better than rotating the array in memory.
+2  A:

Complete real-world code for this problem:

|."1 |: array

The language is J, by K.E. Iverson. http://www.jsoftware.com/

+12  A:

Python:

rotated = zip(*original[::-1])

Cheap, I know.

I believe this code originates from Peter Norvig:http://www.norvig.com/python-iaq.html
Shiiiiii* gotta learn Python.
A:
# include<iostream>
# include<iomanip>

using namespace std;
const int SIZE=3;
void print(int a[][SIZE],int);
void rotate(int a[][SIZE],int);

void main()
{
int a[SIZE][SIZE]={{11,22,33},{44,55,66},{77,88,99}};
cout<<"the array befor rotate\n";

print(a,SIZE);
rotate( a,SIZE);
cout<<"the array after rotate\n";
print(a,SIZE);
cout<<endl;

}

void print(int a[][SIZE],int SIZE)
{
int i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
cout<<a[i][j]<<setw(4);
}

void rotate(int a[][SIZE],int SIZE)
{
int temp[3][3],i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE/2.5;j++)
{
temp[i][j]= a[i][j];
a[i][j]= a[j][SIZE-i-1] ;
a[j][SIZE-i-1] =temp[i][j];

}
}
A:

short normal[4][4] = {{8,4,7,5},{3,4,5,7},{9,5,5,6},{3,3,3,3}};

short rotated[4][4];

for (int r = 0; r < 4; ++r)
{
for (int c = 0; c < 4; ++c)
{
rotated[r][c] = normal[c][3-r];
}
}

Simple C++ method, tho there would be a big memory overhead in a big array.

+1  A:

This a better version of it in Java: I've made it for a matrix with a different width and height

• h is here the height of the matrix after rotating
• w is here the width of the matrix after rotating

public int[][] rotateMatrixRight(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[w - j - 1][i];
}
}
return ret;
}

public int[][] rotateMatrixLeft(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[j][h - i - 1];
}
}
return ret;
}

This code is based on Nick Berardi's post.

A:

PHP:

<?php
\$a = array(array(1,2,3,4),array(5,6,7,8),array(9,0,1,2),array(3,4,5,6));
\$b = array(); //result

while(count(\$a)>0)
{
\$b[count(\$a[0])-1][] = array_shift(\$a[0]);
if (count(\$a[0])==0)
{
array_shift(\$a);
}
}
?>

James Lin [email protected]

A:

All the current solutions have O(n^2) overhead as scratch space (this excludes those filthy OOP cheaters!). Here's a solution with O(1) memory usage, rotating the matrix in-place 90 degress right. Screw extensibility, this sucker runs fast!

#include <algorithm>
#include <cstddef>

// Rotates an NxN matrix of type T 90 degrees to the right.
template <typename T, size_t N>
void rotate_matrix(T (&matrix)[N][N])
{
for(size_t i = 0; i < N; ++i)
for(size_t j = 0; j <= (N-i); ++j)
std::swap(matrix[i][j], matrix[j][i]);
}

DISCLAIMER: I didn't actually test this. Let's play whack-a-bug!

A:

A detailed explanation of Array rotation problem with 7 possible solution with Code and Time & Space Complexities at

http://www.rawkam.com/?p=1008

+1  A:

Slow but simple Ruby-way: .transpose.map &:reverse