CareerCup

Here is my post on rotating a given 2D matrix by a given angle (+90, -90, +180, -180):

rajendrauppal.blogspot.in/2011/12/rotating-2d-array-of-integers-matrix-by.html

Summary:
Input: n by n matrix M, where n >= 2

Rotate by +90 (clock-wise):
Step 1: Transpose M
Step 2: Reverse each row

Rotation by -90 degree (anticlockwise once):
Step 1: Transpose
Step 2: Reverse each column

Rotation by +180 degree (clockwise twice):
Two methods follows

First:
Rotate input matrix +90 degree twice, if routine for which is available to you

Second: (You'll be amazed!)
Step 1: Reverse each row
Step 2: Reverse each column

Rotation by -180 degree (anticlockwise twice): Three(!!!) methods follows

First:
Rotate input matrix -90 degree twice, if routine for which is available to you

Second: (You'll be amazed again!)
Step 1: Reverse each column
Step 2: Reverse each row

Third: (Aha!)
Because rotating a matrix +180 degree or -180 should produce same result. So you can rotate it by +180 degree using one of above methods.

private static int[][] rotateMatrixBy90Degree(int[][] matrix, int n) {
		for (int layer = 0; layer < n / 2; layer++) {
			int first = layer;
			int last = n - 1 - layer;
			for (int i = first; i < last; i++) {
				int offset = i - first;
				int top = matrix[first][i];
				matrix[first][i] = matrix[last - offset][first];
				matrix[last - offset][first] = matrix[last][last - offset];
				matrix[last - offset][last] = matrix[i][last];
				matrix[i][last] = top;
			}
		}
		System.out.println("Matrix After Rotating 90 degree:-");
		printMatrix(matrix, n);
		return matrix;

	}

1:First Take the transpose of the matrix.
2:Reverse Each Row of the matrix.

Code:

#include<stdio.h>

Rotate(int A[4][4],int n)
{
int temp;
int i;
int j;
//Transpose of Matrix.
	for(i=0;i<n;i++)
	{
		for(j=i;j<n;j++)
		{
			temp=A[i][j];
			A[i][j]=A[j][i];
			A[j][i]=temp;
		}
	}
//Reverse Each Row.
	for(i=0;i<n;i++)
	{
		for(j=0;j<n/2;j++)
		{
			temp=A[i][j];
			A[i][j]=A[i][n-j-1];
			A[i][n-j-1]=temp;
		}
	}
}
int main()
{
	int A[4][4]= {{1,2,3,4},
	      {6,7,8,9},
	      {11,12,13,14},
	      {16,17,18,19}};
	int n=4;
	int i;
	int j;
	Rotate(A,n);
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			printf("%d ",A[i][j]);
		}
		printf("\n");
	}

}

int[,] m = new int[,] { { 1, 2, 3, 10 }, { 4, 5, 6, 11 }, { 7, 8, 9, 12 }, {13,14,15,16} };
int ml = 4;
int tmp = 0;
for (int i = 0; i < ml/2; i++)
{
for (int j = i; j < ml-1 - i; j++)
{
tmp = m[i, j];
m[i, j] = m[ml -1 - j, i]; //move up
m[ml - 1 - j, i] = m[ml - 1 - i, ml - 1 - j]; //move left
m[ml - 1 - i, ml - 1 - j] = m[j, ml - 1 - i]; //move donw
m[j, ml - 1 - i] = tmp; //move right
}
}

question from career cup book

public static void rotate(int[][] matrix, int n)
{
for (int layer = 0; layer < n / 2; ++layer)
{
int first = layer;
int last = n - 1 - layer;
for (int i = first; i < last; ++i)
{
int offset = i - first;
int top = matrix[first][i]; // save top
// left -> top
matrix[first][i] = matrix[last - offset][first];

// bottom -> left
matrix[last - offset][first] = matrix[last][last - offset];

// right -> bottom
matrix[last][last - offset] = matrix[i][last];

// top -> right
matrix[i][last] = top; // right <- saved top
}
}
}

void rotateMatrix(float** a, int n) {

if (n <= 1) {
return; // nothing to do: we hit 0 (n is even) or 1 (n is odd)
}

/* outer layer */
for (int i=0; i<n; i++) {
int saved = a[0][i]; // save top.(left+i)

a[0][i] = a[n-i-1][0]; // move (bottom-i).left to top.(left+i)

a[n-i-1][0] = a[n-1][n-1-i]; // move bottom.(right-i) to (bottom-i).left

a[n-1][n-1-i] = a[i][n-1]; // move top(+i).right to bottom.(right-i)

a[i][n-1] = saved; // move top.left (saved) to top(+i).right
}

rotateMatrix(a[1][1], n-2); // now do it for the inner layer(s)
}

2 Steps:
Find transpose
Reverse each row indiv

Two easy steps
1. First find transpose
2. Swap first and last column, second and second last column and so on

Code here

static void rotate90(int[][]a){
        int n = a.length;
                for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
            //Swap a[i][j] and a[j][i]
                a[i][j] = a[i][j] ^ a[j][i];
                a[j][i] = a[j][i] ^ a[i][j];
                a[i][j] = a[i][j] ^ a[j][i];
            }
                }
        
        //Now swap colums
        int i=0;
        int j=n-1;
        while(i<j){
            for(int k=0;k<n;k++){
                //Swap a[k][i] and a[k][j]
                a[k][i] = a[k][i] ^ a[k][j];
                a[k][j] = a[k][j] ^ a[k][i];
                a[k][i] = a[k][i] ^ a[k][j];
            }
            i++;
            j--;
        }                       
}
}

void rotate_matrix(int arr[3][3], int n)
{
	int i;
	int j;
	int *mirror_pos;
	int temp;
	for (i = 0; i < n; ++i) {
		for (j = i + 1; j < n; ++j) {
			mirror_pos = &arr[j][i];
			temp = *mirror_pos;
			*mirror_pos = arr[i][j];
			arr[i][j] = temp;
		}
	}
}

consider the column and row separately.(say,one n by m matrix, all index starts from 0. )
Any element with row # i , will be placed in the i-th column in the result matrix.
Any element with column #i, will be placed in the i-th row
So the problem is solved:
new_i, new_j = j,i
tips: the result matrix is m by n

static void Main(string[] args)
{
    int[,] Matr;
    int Sz = 5;
    Matr = new int[Sz, Sz];
    // initialize matrix
    for (int i = 0; i < Sz; i++)
         for (int j = 0; j < Sz; j++)
              Matr[i, j] = i * Sz + j + 1;
    // rotate
    for (int i = 0; i < (Sz - Sz % 2) / 2; i++)
    {
         for (int j = i; j < Sz - i - 1; j++)
         {
              SWAP(ref Matr[i, j], ref Matr[j, Sz - i - 1]);
              SWAP(ref Matr[Sz - j - 1, i], ref Matr[i, j]);
              SWAP(ref Matr[Sz - i - 1, Sz - j - 1], ref Matr[Sz - j - 1, i]);
          }
    }
}

public static void SWAP(ref int a, ref int b)
{
    a = a + b;
    b = a - b;
    a = a - b;
}

This will work for [n][n] matrix. Code in Javascript.

var rotateMat = function(matrix){
var mat = matrix;
var numRows = mat.length; var numCols = mat[0].length;

for(var i = 0 ; i < numRows ; i++ )
for(var j = i ; j < numCols ; j++)
{
var tmp = mat[i][j];
mat[i][j] = mat[j][i];
mat[j][i] = tmp;
console.log(tmp);
}
console.log(mat);


var start = 0; end = numCols - 1;
while(start<end){
for(var i = 0 ; i < numRows; i++){
var tmp = mat[i][start];
mat[i][start] = mat[i][end];
mat[i][end] = tmp;
}
start++; end--;
}
console.log(mat);
}

This one was tested on work. C#

int size = 2; //that means size 3x3 because counting starts from 0
int[,] ar = new int[3,3] { {1, 2,3}, {4,5,6},{7,8,9} };

//layers - how many layers can be "peeled" from the matrix.
//2x2 - 1 layer. 3x3 - 1 layer (with one unrotated element in the middle), 4x4 - 2 layers
int layers = (int)Math.Floor((double)(size+1) /2);

//starting rotate layer by layer starting from the outside layer.
for (int lyr = 0; lyr < layers; lyr++)
{
for (int col = lyr; col < size - lyr; col++)
{
int temp = ar[size-lyr-col,lyr];
ar[size - lyr - col, lyr] = ar[size - lyr, size - lyr - col];
ar[size - lyr, size - lyr - col] = ar[lyr + col, size - lyr];
ar[lyr + col, size - lyr] = ar[lyr, lyr + col];
ar[lyr, lyr + col]= temp;
}
}

This one was tested. It works. C#

int size = 2; //that means size 3x3 because counting starts from 0
int[,] ar = new int[3,3] { {1, 2,3}, {4,5,6},{7,8,9} };

//layers - how many layers can be "peeled" from the matrix.
//2x2 - 1 layer. 3x3 - 1 layer (with one unrotated element in the middle), 4x4 - 2 layers
int layers = (int)Math.Floor((double)(size+1) /2);

//starting rotate layer by layer starting from the outside layer.
for (int lyr = 0; lyr < layers; lyr++)
{
for (int col = lyr; col < size - lyr; col++)
{
int temp = ar[size-lyr-col,lyr];
ar[size - lyr - col, lyr] = ar[size - lyr, size - lyr - col];
ar[size - lyr, size - lyr - col] = ar[lyr + col, size - lyr];
ar[lyr + col, size - lyr] = ar[lyr, lyr + col];
ar[lyr, lyr + col]= temp;
}
}

#include<iostream>
using namespace std;
#define MAX_SIZE 50
int n[MAX_SIZE][MAX_SIZE];
int size,temp;
int main()
{


    cout<<"Enter the size of aquare matrix : ";
    cin>>size;

    cout<<"\nEnter the array : ";
    for(int i=0; i<size; i++)
    {
        for(int j =0; j<size; j++)
            cin>>n[i][j];
    }

    cout<<"\nEntered array id : ";

    for(int i=0; i<size; i++)
    {
        cout<<endl;
        for(int j =0; j<size; j++)
            cout<<n[i][j]<<" ";
    }

    //transforming the matrix
    for(int i=0; i<size-1; i++)
    {
        for(int j =i+1; j<size; j++)
           {
               temp =n[i][j];
               n[i][j] = n[j][i];
               n[j][i] =temp;
           }
    }

    //upside down the matrix

    for(int i=0; i<size/2; i++)
    {
        for(int j =0; j<size; j++)
        {
            temp =n[i][j];
            n[i][j] = n[size-1-i][j];
            n[size-1-i][j] = temp;
        }
    }

    cout<<"\nRotated array is : ";

    for(int i=0; i<size; i++)
    {
        cout<<endl;
        for(int j =0; j<size; j++)
            cout<<n[i][j]<<" ";
    }
    return 0;
}

This one works too.
It simulates the rotation. Though it's O(n^2).

1 2 3 4 5
0 5 6 7 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
------------
0,0 --> 0,4
0,4 --> 4,4
4,4 --> 4,0
4,0 --> 0,0
***
0,1 --> 1,4
1,4 --> 4,3
4,3 --> 3,0
3,0 --> 0,1
***
0,2 --> 2,4
2,4 --> 4,2
4,2 --> 2,0
2,0 --> 0,2
***
0,3 --> 3,4
3,4 --> 4,1
4,1 --> 1,0
1,0 --> 0,3
***
1,1 --> 1,3
1,3 --> 3,3
3,3 --> 3,1
3,1 --> 1,1
***
1,2 --> 2,3
2,3 --> 3,2
3,2 --> 2,1
2,1 --> 1,2
***
0 0 0 0 1
0 0 0 5 2
0 0 0 6 3
0 0 0 7 4
0 0 0 0 5

package Rotate;

public class RotateClean {

	public static void main(String args[]) {
		int[][] a = { { 1, 2, 3, 4, 5 }, { 0, 5, 6, 7, 0 }, { 0, 0, 0, 0, 0 },
				{ 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 } };
		rotate(a);
	}

	static void rotate(int[][] a) {
		int temp0, temp1;
		int n = a.length;
		int m = n / 2;

		print(a);

		System.out.println("------------");

		for (int j = 0; j < m; j++) {
			for (int i = j; i < n - j - 1; i++) {

				temp0 = a[i][n - 1 - j];
				a[i][n - 1 - j] = a[j][i];

				temp1 = a[n - 1 - j][n - 1 - j - (i - j)];
				a[n - 1 - j][n - 1 - j - (i - j)] = temp0;

				temp0 = a[n - 1 - j - (i - j)][j];
				a[n - 1 - j - (i - j)][j] = temp1;

				a[j][i] = temp0;

			}
		}
		print(a);
	}

	static void print(int[][] a) {

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {

				System.out.print(a[i][j] + " ");
			}
			System.out.println("");

		}
	}
}

for(int i = 0 ; i < n/2 ; i++){
for(int j = i ; j < n-i ; j++){
//4 corners = i,j - j,n-1-i - n-1-i,n-1-j - n-1-j,i
swap(&mat[i][j] , &mat[j][n-1-i]);
swap(&mat[i][j] , &mat[n-1-i][n-1-j]);
swap(&mat[i][j] , &mat[n-1-j][i]);
}
}

for(int i = 0 ; i < n/2 ; i++){
for(int j = i ; j < n-i ; j++){
//4 corners = i,j - j,n-1-i - n-1-i,n-1-j - n-1-j,i
swap(&mat[i][j] , &mat[j][n-1-i]);
swap(&mat[i][j] , &mat[n-1-i][n-1-j]);
swap(&mat[i][j] , &mat[n-1-j][i]);
}
}

#include <iostream>
#include <cstdlib>
using namespace std;
const int SZ = 5;
void Init(char mtrx[][SZ])
{
    for (int y = 0; y < SZ; ++y)
        for (int x = 0; x < SZ; ++x)
            mtrx[x][y] = '0' + (rand() % 10);
}
void Print(char mtrx[][SZ])
{
    for (int y = 0; y < SZ; ++y)
    {
        for (int x = 0; x < SZ; ++x)
            cout << mtrx[x][y];
        cout << endl;
    }
    cout << endl;
}
void Swap4(char mtrx[][SZ], int x, int y)
{
    const int sz = SZ - 1;
    char& c1 = mtrx[x][y];
    char& c2 = mtrx[sz - y][x];
    char& c3 = mtrx[sz - x][sz - y];
    char& c4 = mtrx[y][sz - x];
    char tmp = c4;
    c4 = c3;
    c3 = c2;
    c2 = c1;
    c1 = tmp;
}
void Rotate(char mtrx[][SZ])
{ 
    for (int y = 0; y < (SZ + 1) / 2; ++y)
        for (int x = 0; x < (SZ) / 2; ++x)
            Swap4(mtrx, x, y);
}
int main()
{
    char (*mtrx)[SZ] = new char[SZ][SZ];
    Init(mtrx);
    Print(mtrx);
    Rotate(mtrx);
    Print(mtrx);
    delete[] mtrx;
}

public void rotateMatrix(int[][] a, int n){
		for(int level=0;level<n/2;level++){
			for(int j=level;j<n-level-1;j++){
				int temp=a[level][j];
				a[level][j] = a[n-1-j][level];
				a[n-1-j][level] = a[n-1-level][n-1-j];
				a[n-1-level][n-1-j]=a[j][n-1-level];
				a[j][n-1-level]=temp;
			}
		}
	}

def rotate_matrix( input ):
    n = len( input )
    for r in range( 0, n/2 ):
        for o in range( r, n-r-1 ):
            temp = input[ r ][ o ]
            input[ r ][ o ]=input[ n-o-1 ][ r ]
            input[ n-o-1 ][ r ]=input[ n-r-1 ][ n-o-1 ]
            input[ n-r-1 ][ n-o-1 ]=input[ o ][ n-r-1 ]
            input[ o ][ n-r-1 ]=temp
    return input