In Place Matrix (2D Array) Clockwise and Counterclockwise Rotation – 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 does not take extra buffer i.e. does the stuff IN-PLACE. There is another article in this blog where I have implemented this using 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 NxN array 90 degrees using no extra buffer.
   e.g. 
     [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24, 25]]
	 
	 should appear as
	 
	 [[5, 10, 15, 20, 25], [4, 9, 14, 19, 24], [3, 8, 13, 18, 23], [2, 7, 12, 17, 22], [1, 6, 11, 16, 21]]
	 for a 90 degrees counter clockwise rotation

	 
	 [[21, 16, 11, 6, 1], [22, 17, 12, 7, 2], [23, 18, 13, 8, 3], [24, 19, 14, 9, 4], [25, 20, 15, 10, 5]]
	 for a 90 degrees clockwise rotation
	 
 */

public class Rotate2DArrayInPlace {
		
public static void main (String args [] ) throws Exception {
		
		Integer [] [] myNxNArray = new Integer [][] {
			{1, 2, 3, 4, 5},
			{6, 7, 8, 9, 10},
			{11, 12, 13, 14, 15},
			{16,17,18,19,20},
			{21,22,23,24,25}
		};
		
		System.out.println("SOURCE ARRAY: \n" + Arrays.deepToString(myNxNArray));
		Integer [][] rotatedInPlace = rotateMatrixInPlaceCounterClockwise(myNxNArray);
		
		System.out.println("ROTATED IN PLACE - 90 degrees COUNTER CLOCKWISE");
		System.out.println(Arrays.deepToString(rotatedInPlace));
		
		//The array referenced in above definition myNxNArray is changed so you will need to redefine
		Integer [] [] myNxNArray1 = new Integer [][] {
			{1, 2, 3, 4, 5},
			{6, 7, 8, 9, 10},
			{11, 12, 13, 14, 15},
			{16,17,18,19,20},
			{21,22,23,24,25}
		};
		
		Integer [][] rotatedInPlaceClockwise = rotateMatrixInPlaceClockwise(myNxNArray1);
		
		System.out.println("ROTATED IN PLACE - 90 degrees CLOCKWISE");
		System.out.println(Arrays.deepToString(rotatedInPlaceClockwise));
		
	}
	
	/**
	 * This method rotates the matrix 90 degrees counter clockwise without using extra buffer..
	 */
	public static Integer[][] rotateMatrixInPlaceCounterClockwise(Integer[][] matrix) throws Exception {
		
		if(matrix.length == 0 || matrix.length != matrix[0].length) {
			throw new Exception ("Invalid Input");
		}

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

		}
		return matrix;
	}
	
	/**
	 * This method rotates the matrix 90 degrees counter clockwise without using extra buffer..
	 */
	public static Integer[][] rotateMatrixInPlaceClockwise(Integer[][] matrix) throws Exception {
		
		if(matrix.length == 0 || matrix.length != matrix[0].length) {
			throw new Exception ("Invalid Input");
		}

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

		}
		return matrix;
	}

}

OUTPUT:

SOURCE ARRAY: 
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24, 25]]
ROTATED IN PLACE - 90 degrees COUNTER CLOCKWISE
[[5, 10, 15, 20, 25], [4, 9, 14, 19, 24], [3, 8, 13, 18, 23], [2, 7, 12, 17, 22], [1, 6, 11, 16, 21]]
ROTATED IN PLACE - 90 degrees CLOCKWISE
[[21, 16, 11, 6, 1], [22, 17, 12, 7, 2], [23, 18, 13, 8, 3], [24, 19, 14, 9, 4], [25, 20, 15, 10, 5]]

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]]

Array Max Integer Finder (With Big O Analysis)

This tutorial shows you an implementation of three different methods of searching for the maximum number in an Integer array. The array is assumed to hold positive integers.

  1. First method findMaxCompareMax() assumes the first number on the array to be maximum and the loops through other numbers in sequence and replaces the current maximum with the new maximum. When all the elements are checked, we have a maximum number.
  2. The second method findMaxCompareAll() takes an array element and compares it with every other element in the array to see if it is maximum. If it is not, then it proceeds with the next element.
  3. The third method findMaxCompareAfterIndex() This method takes an array element and compare it with other elements in the array to see if it is maximum. If it is not, then it proceeds with the next element. However, this method does not compare every element from the beginning. To avoid redundant comparing, it only compares with the remaining elements in the array (i.e. position + 1 onwards)

Check the code comments for the Big O Analysis of these three methods.

package com.icodejava.blog.published.search;

import java.util.Arrays;

/**
 * 
 * This class is used to demonstrate 3 different ways of finding a maximum
 * number in an Integer Array holding positive integer numbers.
 * 
 * Also provides a Big O analysis.
 */
public class MaxIntegerFinder {

    public static void main(String args[]) {

        int[] numbers = {5, 4, 9, 2, 2, 1, 10, 21, 6 };
        
        System.out.println("Source Array " + Arrays.toString(numbers));

        findMaxCompareMax(numbers);

        findMaxCompareAll(numbers);

        findMaxCompareAfterIndex(numbers);

    }


    /**
     * This method assumes the first number on the array to be the maximum
     * You can also assume the last one to be the max and compare it in reverse.
     * It then loops through other numbers in the array and replaces the 
     * current maximum with the new maximum it finds.
     * 
     * Complexity: O(n) where n is the number of elements in the array
     */
    private static int findMaxCompareMax(int[] numbers) {

        if (numbers.length < 1 ) {
            return 0;
        }
        
        int currentMax = numbers[0];
        for (int i = 1 ; i < numbers.length; i++) { if(numbers[i] > currentMax) {
                currentMax = numbers[i];
            }
        }
        
        System.out.println("Max Number using findMaxCompareMax -> " + currentMax);
        return currentMax;
        
    }
    
    /**
     * This method takes an array element and compare it with 
     * every other element in the array to see if it is maximum.
     * 
     * If it is not, then it proceeds with the next element
     * 
     * Complexity: O(n^2) in worst case and O(n) in best case 
     * where n is the number of elements in the array
     * 
     * Best case scenario is where the first element itself is maximum
     * Worst case scenario is where the last element is maximum.
     */
    private static int findMaxCompareAll(int[] numbers) {

        if (numbers.length < 1) {
            return 0;
        }

        int max = -1;

        for (int i = 0; i < numbers.length; i++) {
            for (int j = 0; j < numbers.length; j++) {
                if (max < numbers[j]) { max = numbers[j]; break; } } } System.out.println("Max Number using findMaxCompareAll -> " + max);
        return max;

    }
    
    /**
     * This method takes an array element and compare it with 
     * other elements in the array to see if it is maximum.
     * 
     * If it is not, then it proceeds with the next element. 
     * 
     * However, this method does not compare every element from the beginning. 
     * To avoid redundant comparing, it only compares with the remaining elements
     * in the array (i.e. position + 1 onwards)
     * 
     * Complexity: O(n^2) in worst case and O(n) in best case 
     * where n is the number of elements in the array
     * 
     * Best case scenario is where the first element itself is maximum
     * Worst case scenario is where the last element is maximum.
     */
    private static int findMaxCompareAfterIndex(int[] numbers) {

        if (numbers.length < 1 ) {
            return 0;
        }
        
        int max=-1;
        
        for (int i = 0 ; i < numbers.length; i++) {
            for(int j = i ; j< numbers.length; j++) {
                if(max < numbers [j]) { max = numbers[j]; break; } } } System.out.println("Max Number using findMaxCompareAfterIndex -> " + max);
        return max;
    }

}

OUTPUT:

Source Array [5, 4, 9, 2, 2, 1, 10, 21, 6]
Max Number using findMaxCompareMax -> 21
Max Number using findMaxCompareAll -> 21
Max Number using findMaxCompareAfterIndex -> 21