How do you rotate a two dimensional array?

Question

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?

Answer 1

here is my In Place implementation in C

void rotateRight(int matrix[][SIZE], int length) {

    int layer = 0;

    for (int layer = 0; layer < length / 2; ++layer) {

        int first = layer;
        int last = length - 1 - layer;

        for (int i = first; i < last; ++i) {

            int topline = matrix[first][i];
            int rightcol = matrix[i][last];
            int bottomline = matrix[last][length - layer - 1 - i];
            int leftcol = matrix[length - layer - 1 - i][first];

            matrix[first][i] = leftcol;
            matrix[i][last] = topline;
            matrix[last][length - layer - 1 - i] = rightcol;
            matrix[length - layer - 1 - i][first] = bottomline;
        }
    }
}

Answer 2

Python:

rotated = zip(*original[::-1])  # On Python 3, list(zip(*original[::-1]))

Cheap, I know.

And counterclockwise:

rotated_ccw = zip(*original)[::-1]  # On Python 3, list(zip(*original))[::-1]

How this works: (Requested in comments)

zip(*original) will swap axes of 2d arrays by stacking corresponding items from lists into new lists. (The * operator tells the function to distribute the contained lists into arguments)

>>> zip(*[[1,2,3],[4,5,6],[7,8,9]])
[[1,4,7],[2,5,8],[3,6,9]]

The [::-1] statement reverses array elements (please see Extended Slices).

>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]

Finally, combining the two will result in the rotation transformation.

The change in placement of [::-1] will reverse lists in different levels of the matrix.

Answer 3

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.

Answer 4

Ruby-way: .transpose.map &:reverse

Answer 5

There are a lot of answers already, and I found two claiming O(1) time complexity. The real O(1) algorithm is to leave the array storage untouched, and change how you index its elements. The goal here is that it does not consume additional memory, nor does it require additional time to iterate the data.

Rotations of 90, -90 and 180 degrees are simple transformations which can be performed as long as you know how many rows and columns are in your 2D array; To rotate any vector by 90 degrees, swap the axes and negate the Y axis. For -90 degree, swap the axes and negate the X axis. For 180 degrees, negate both axes without swapping.

Further transformations are possible, such as mirroring horizontally and/or vertically by negating the axes independently.

This can be done through e.g. an accessor method. The examples below are JavaScript functions, but the concepts apply equally to all languages.

 // Get an array element in column/row order
 var getArray2d = function(a, x, y) {
   return a[y][x];
 };

 //demo
 var arr = [
   [5, 4, 6],
   [1, 7, 9],
   [-2, 11, 0],
   [8, 21, -3],
   [3, -1, 2]
 ];

 var newarr = [];
 arr[0].forEach(() => newarr.push(new Array(arr.length)));

 for (var i = 0; i < newarr.length; i++) {
   for (var j = 0; j < newarr[0].length; j++) {
     newarr[i][j] = getArray2d(arr, i, j);
   }
 }
 console.log(newarr);

// Get an array element rotated 90 degrees clockwise
function getArray2dCW(a, x, y) {
  var t = x;
  x = y;
  y = a.length - t - 1;
  return a[y][x];
}

//demo
var arr = [
  [5, 4, 6],
  [1, 7, 9],
  [-2, 11, 0],
  [8, 21, -3],
  [3, -1, 2]
];

var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));

for (var i = 0; i < newarr.length; i++) {
  for (var j = 0; j < newarr[0].length; j++) {
    newarr[i][j] = getArray2dCW(arr, i, j);
  }
}
console.log(newarr);

// Get an array element rotated 90 degrees counter-clockwise
function getArray2dCCW(a, x, y) {
    var t = x;
    x = a[0].length - y - 1;
    y = t;
    return a[y][x];
  }
  //demo
var arr = [
  [5, 4, 6],
  [1, 7, 9],
  [-2, 11, 0],
  [8, 21, -3],
  [3, -1, 2]
];

var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));

for (var i = 0; i < newarr.length; i++) {
  for (var j = 0; j < newarr[0].length; j++) {
    newarr[i][j] = getArray2dCCW(arr, i, j);
  }
}
console.log(newarr);

// Get an array element rotated 180 degrees
function getArray2d180(a, x, y) {
    x = a[0].length - x - 1;
    y = a.length - y - 1;
    return a[y][x];
  }
  //demo
var arr = [
  [5, 4, 6],
  [1, 7, 9],
  [-2, 11, 0],
  [8, 21, -3],
  [3, -1, 2]
];

var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));

for (var i = 0; i < newarr.length; i++) {
  for (var j = 0; j < newarr[0].length; j++) {
    newarr[i][j] = getArray2d180(arr, i, j);
  }
}
console.log(newarr);

This code assumes an array of nested arrays, where each inner array is a row.

The method allows you to read (or write) elements (even in random order) as if the array has been rotated or transformed. Now just pick the right function to call, probably by reference, and away you go!

The concept can be extended to apply transformations additively (and non-destructively) through the accessor methods. Including arbitrary angle rotations and scaling.

Answer 6

here's a in-space rotate method, by java, only for square. for non-square 2d array, you will have to create new array anyway.

private void rotateInSpace(int[][] arr) {
    int z = arr.length;
    for (int i = 0; i < z / 2; i++) {
        for (int j = 0; j < (z / 2 + z % 2); j++) {
            int x = i, y = j;
            int temp = arr[x][y];
            for (int k = 0; k < 4; k++) {
                int temptemp = arr[y][z - x - 1];
                arr[y][z - x - 1] = temp;
                temp = temptemp;

                int tempX = y;
                y = z - x - 1;
                x = tempX;
            }
        }
    }
}

code to rotate any size 2d array by creating new array:

private int[][] rotate(int[][] arr) {
    int width = arr[0].length;
    int depth = arr.length;
    int[][] re = new int[width][depth];
    for (int i = 0; i < depth; i++) {
        for (int j = 0; j < width; j++) {
            re[j][depth - i - 1] = arr[i][j];
        }
    }
    return re;
}