Rotate an N*N matrix

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

My initial thoughts:

  1. I can’t come up with a way to do this in place so I need additional memory.
  2. I copy the 1st row and last column to the corresponding positions. The mapping is given by (0,i)->(i,N-1) and (i,N-1)->(N-1,N-i-1).
  3. Then recursively process the inner (N-1)*(N-1) matrix.

My initial codes:

	public static void rotate90Degree(int[][] matrix, int[][] result) {
		int N = matrix.length;
		for (int i = 0; i < N; ++i) {
			result[i][N - 1] = matrix[0][i];
			result[N - 1][N - i - 1] = matrix[i][N - 1];
		}
		if (N == 1)
			return;
		else {
			int[][] part = new int[N - 1][N - 1];
			for (int i = 1; i < N; ++i) {
				for (int j = 0; j < N - 1; ++j)
					part[i - 1][j] = matrix[i][j];
			}
			rotate90Degree(part, result);
		}
	}

Comments after running:

  1. It works fine.
  2. Time/Space complexity O(n^2). Too much space for large matrix.

Solutions:
Somehow the solution’s code does not work for me. The idea is clear though: each time we do a 4-way swap for the elements in the windmill positions.
Below is the correct version of code:

	public static void rotate(int[][] matrix) {
		int N = matrix.length;
		for(int i = 0; i < N/2; ++i) {
			for(int j = 0; j < (N+1)/2; ++j) {
				int temp = matrix[i][j];
				matrix[i][j] = matrix[N-1-j][i];
				matrix[N-1-j][i] = matrix[N-1-i][N-1-j];
				matrix[N-1-i][N-1-j] = matrix[j][N-1-i];
				matrix[j][N-1-i] = temp;
			}
		}
	}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: