CC_1_6

MatrixRotation.java

// Cracking the Coding Interview
// 1.6 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?
import java.util.Arrays;
class MatrixRotation {
	// assuming the matrix is NxN
	public static void rotateMatrix(int[][] m) {
		if (m == null || m.length <= 1) return; 
		int len = m.length;
		for(int i = 0; i < len/2; i++) {
			for(int j = 0; j < (len+1)/2; j++) {
				int tmp = m[i][j];
				int prev = m[i][j];
				int nexti = len-j-1;
				int nextj = i;

				for(int k = 0; k < 4; k++) {
					tmp = m[nexti][nextj];
					m[nexti][nextj] = prev;
					prev = tmp;
					// be careful!
					int tmpi = nexti;
					nexti = len-nextj-1;
					nextj = tmpi;
				}
			}
		}
	}

	public static void main(String[] args) {
		int[][] test1 = new int[][] {{0}};
		int[][] test2 = new int[][] {{1, 2}, 
									 {3, 4}};
		int[][] test3 = new int[][] {{1, 2, 3}, 
									 {4, 5, 6}, 
									 {7, 8, 9}};
		int[][] result1 = new int[][] {{0}};
		int[][] result2 = new int[][] {{2, 4}, 
									   {1, 3}};
		int[][] result3 = new int[][] {{3, 6, 9}, 
									   {2, 5, 8}, 
									   {1, 4, 7}};	
		rotateMatrix(test1);
		rotateMatrix(test2);
		rotateMatrix(test3);							
		assert areEqual(test1, result1);
		assert areEqual(test2, result2);
		assert areEqual(test3, result3);
		System.out.println("Test Passed\n");
	}
	private static boolean areEqual(int[][] arr1, int[][] arr2) {
		if (arr1 == arr2) return true;
		if (arr1 == null || arr2 == null || arr1.length != arr2.length) return false;
		for(int i = 0; i < arr1.length; i++) {
			if (!Arrays.equals(arr1[i], arr2[i])) return false;
		}
		return true;
	}

}