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

  1. Recursively Finding Greatest Common Divisor (GCD) – Java Implementation
  2. Implementing a Simple LIFO Stack in Java using LinkedList
  3. Implementing a Simple FIFO Queue in Java Using Linked List
  4. In Place Matrix (2D Array) Clockwise and Counterclockwise Rotation – Java Implementation
  5. Matrix (2D Array) Clockwise and Counterclockwise Rotation with Extra Buffer – Java Implementation
  6. Array Max Integer Finder (With Big O Analysis)
  7. A Basic Implementation of Binary Tree in Java
  8. A Basic Implementation of Generic Tree in Java
  9. Basic example of implementing Singly Linked List in Java
  10. Prime Number Finder In Java
  11. Printing Fibonacci Sequence Using Recursive and Iterative Methods
  12. Finding Square Root Of A Double Number In Java Using Binary Search
  13. How to Add and Remove nodes in an unsorted Linked List
  14. How to swap two variables without using extra temporary variable?
  15. Rotating a two dimensional integer array In-Place and using extra memory
  16. How to reverse a Singly Linked List iteratively and recursively
  17. Sorted Circular Linked List Implementation And Insert Operation
  18. Finding Mean Value Of An Integer Array In Java
  19. How to intersect two sets in Java using java.util.Set data structure.
  20. Bubble Sorting An Integer Array In Ascending and Descending Order
  21. How to split strings and separate the words with spaces
  22. How to easily sort characters in a String?
Tagged , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *