Matrix (2D Array) Clockwise and Counterclockwise Rotation with Extra Buffer – Java Implementation

Below, you will find a java implementation of class that does a matrix or 2 dimensional array rotation both clockwise and anti clockwise. The approach used here takes extra buffer. There is another article in this blog where I have implemented this in place i.e. without requiring extra buffer space.

package com.icodejava.blog.published.maths;

import java.util.Arrays;

/**
 * 
 * @author Kushal Paudyal 
 * Created on: 01/05/2017 
 * Last Modified on: 01/05/2017
 *
 * This class demonstrates how to rotate a mxn array 90 degrees using extra buffer
   e.g. 
     1  2  3 4 5
	 6  7  8 9 10
	 11 12 13 14 15
	 
	 should appear as
	 
	 11 6 1
	 12 7 2
	 13 8 3
	 14 9 4
	 15 10 5
	 
	 for a 90 degrees clockwise rotation
	 
	 and 
	 
	 5 10 15
	 4 9 14
	 3 8 13
	 2 7 12
	 1 6 11
	 
	 for a 90 degrees counterclockwise rotation
 */
public class Rotate2DArray {

	public static void main(String args[]) throws Exception {

		// define two dimensional array
		Integer[][] myArray = new Integer[][] { 
				{ 1, 2, 3, 4, 5 }, 
				{ 6, 7, 8, 9, 10 }, 
				{ 11, 12, 13, 14, 15 } 
			};

		System.out.println("SOURCE ARRAY: \n" + Arrays.deepToString(myArray));

		Integer[][] rotated = rotateMatrixClockwise(myArray);

		System.out.println("ROTATED ARRAY 90 degrees clockwise:");
		System.out.println(Arrays.deepToString(rotated));
		
		// define two dimensional array
		Integer[][] myArray1 = new Integer[][] { 
				{ 1, 2, 3, 4, 5 }, 
				{ 6, 7, 8, 9, 10 }, 
				{ 11, 12, 13, 14, 15 } 
			};

		System.out.println("SOURCE ARRAY: \n" + Arrays.deepToString(myArray1));

		Integer[][] rotated1 = rotateMatrixCounterClockwise(myArray1);

		System.out.println("ROTATED ARRAY 90 degrees counter clockwise:");
		System.out.println(Arrays.deepToString(rotated1));

	}

	/**
	 * This method rotates the matrix 90 degrees clockwise by using extra
	 * buffer.
	 */
	public static Integer[][] rotateMatrixClockwise(Integer[][] matrix) {
		Integer[][] rotated = new Integer[matrix[0].length][matrix.length];

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

				
				rotated[i][j] = matrix[matrix.length - j - 1][i];
				
			}
		}

		return rotated;
	}
	
	/**
	 * This method rotates the matrix 90 degrees counter clockwise by using extra
	 * buffer.
	 */
	public static Integer[][] rotateMatrixCounterClockwise(Integer[][] matrix) {
		Integer[][] rotated = new Integer[matrix[0].length][matrix.length];

		for (int i = 0; i < matrix[0].length; ++i) {
			for (int j = 0; j < matrix.length; ++j) {
				
				rotated[i][j] = matrix[j][matrix[0].length - i - 1];
			}
		}

		return rotated;
	}

}

OUTPUT:

SOURCE ARRAY: 
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]]
ROTATED ARRAY 90 degrees clockwise:
[[11, 6, 1], [12, 7, 2], [13, 8, 3], [14, 9, 4], [15, 10, 5]]
SOURCE ARRAY: 
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]]
ROTATED ARRAY 90 degrees counter clockwise:
[[5, 10, 15], [4, 9, 14], [3, 8, 13], [2, 7, 12], [1, 6, 11]]

Rotating a two dimensional integer array In-Place and using extra memory

A 3×3 Two dimensional matrix

This is one of the popular interview questions. Interviewees are asked to rotate to the right or to the left an array. Make sure you ask the right question before you begin:

  • What kind of array are you rotating (Integer/ String / Objects?)
  • Do you want the rotation to be in place? (In case there is no extra memory available)
  • Or do you have extra space to do the rotation?

I have used integer array for rotation. However, you should be able to modify it for other data types easily. The example below does rotations using two ways:

  • In-place
  • Using extra space

I tried to calculate the time taken to do the rotation, but with my high end laptop, the time taken to rotate a 4×4 array was below zero ms. It could be different on your machine depending on the speed of your computing device.

Java Implementation:

package com.icodejava.blog.datastructure;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Mar 1, 2014
 * Last Modified On - Mar 1, 2014
 */
public class Matrix2DRotate {

	static int[][] twoDimensionalArray = new int[][]
			{ { 1, 2, 3, 4 },
			{ 5, 6, 7, 8 },
			{ 9, 10, 11, 12 },
			{ 13, 14, 15, 16 }

	};

	public static void main(String[] args) {

		System.out.println("\n\nINPUT ARRAY");

		printTwoDimensionalArray(twoDimensionalArray);

		System.out.print("\n\nROTATED WITH EXTRA SPACE:");

		int[][] rotatedArray = rotate2DArray(twoDimensionalArray);

		printTwoDimensionalArray(rotatedArray);

		System.out.print("\n\nROTATED WITH IN PLACE ROTATION:");

		rotatedArray = rotateInPlace(twoDimensionalArray, 4);

		printTwoDimensionalArray(rotatedArray);
	}

	/**
	 * @param array - two dimensional array
	 * @return Array rotated to right using extra space.
	 */
	private static int[][] rotate2DArray(int[][] array) {
		long startTime = System.currentTimeMillis();
		int length = array[0].length;
		int[][] tempArray = new int[length][length];

		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				tempArray[i][j] = array[length - 1 - j][i];
			}

		}

		long endTime = System.currentTimeMillis();
		printTimeTaken(startTime, endTime);

		return tempArray;
	}

	private static void printTimeTaken(long startTime, long endTime) {

		// System.out.print("StartTime: " + startTime +" endTime: " + endTime);

		if (startTime <= 0 || endTime <= 0 || startTime > endTime) {
			return;
		}

		System.out.println("Took " + (endTime - startTime) + " ms");

	}

	/**
	 * This method rotates a two dimensional matrix in layers.
	 * Portion of this code is taken from Cracking The Coding Interview Book
	 * @param matrix - Two Dimensional Matrix
	 * @param size - size of Matrix
	 * @return In Place Rotated Matrix
	 */
	public static int[][] rotateInPlace(int[][] matrix, int size) {

		long startTime = System.currentTimeMillis();

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

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

			for (int i = first; i < last; ++i) { 				int offset = i - first; 			 				//Saves the top value 				int top = matrix[first][i];  				 				// 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 			}
		}

		long endTime = System.currentTimeMillis();
		printTimeTaken(startTime, endTime);

		return matrix;
	}

	/**
	 * This method prints the two dimensional array to System Console
	 */
	private static void printTwoDimensionalArray(int[][] intArray) {
		for (int i = 0; i < intArray[0].length; i++) {
			for (int j = 0; j < intArray[i].length; j++) {
				System.out.print(intArray[i][j] + "\t");
			}
			System.out.println();
		}

	}
}

Output of running above program:

INPUT ARRAY
1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

ROTATED WITH EXTRA SPACE:Took 0 ms
13	9	5	1
14	10	6	2
15	11	7	3
16	12	8	4

ROTATED WITH IN PLACE ROTATION:Took 0 ms
13	9	5	1
14	10	6	2
15	11	7	3
16	12	8	4