Rotate 2D matrix by 90 degrees - Java
O(n^2) time and O(1) space algorithm
Rotate by +90:
- Transpose
- Reverse each row
Rotate by -90:
- Transpose
- Reverse each column
Rotate by +180:
Method 1: Rotate by +90 twice
Method 2: Reverse each row and then reverse each column
Rotate by -180:
Method 1: Rotate by -90 twice
Method 2: Reverse each column and then reverse each row
Method 3: Reverse by +180 as they are same
--------------------------------------------------------------------------------------------------------
public class Rotate90 {
public static void main(String[] args) {
int[][] original = new int[][] { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
rotateBy90Right(original);
}
private static void rotateBy90Right(int[][] original) {
print(original);
System.out.println("-----------------------------");
System.out.println("Transpose");
int[][] transpos = transpose(original);
print(transpos);
System.out.println("-----------------------------");
System.out.println("Swap Rows");
int[][] rot90Right = swapRows(transpos);
print(rot90Right);
System.out.println("-----------------------------");
}
private static void print(int[][] original) {
for (int i = 0; i < original.length; i++) {
for (int j = 0; j < original[i].length; j++) {
System.out.print(original[i][j] + " ");
}
System.out.print("\n");
}
}
private static int[][] transpose(int[][] array) {
if (array == null || array.length == 0)//empty or unset array, nothing do to here
return array;
int width = array.length;
int height = array[0].length;
int[][] array_new = new int[height][width];
for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
array_new[y][x] = array[x][y];
}
}
return array_new;
}
private static int[][] swapRows(int[][] m) {
for (int i = 0, k = m.length - 1; i < k; ++i, --k) {
int[] x = m[i];
m[i] = m[k];
m[k] = x;
}
return m;
}
}
public static void main(String[] args) {
int[][] original = new int[][] { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
rotateBy90Right(original);
}
private static void rotateBy90Right(int[][] original) {
print(original);
System.out.println("-----------------------------");
System.out.println("Transpose");
int[][] transpos = transpose(original);
print(transpos);
System.out.println("-----------------------------");
System.out.println("Swap Rows");
int[][] rot90Right = swapRows(transpos);
print(rot90Right);
System.out.println("-----------------------------");
}
private static void print(int[][] original) {
for (int i = 0; i < original.length; i++) {
for (int j = 0; j < original[i].length; j++) {
System.out.print(original[i][j] + " ");
}
System.out.print("\n");
}
}
private static int[][] transpose(int[][] array) {
if (array == null || array.length == 0)//empty or unset array, nothing do to here
return array;
int width = array.length;
int height = array[0].length;
int[][] array_new = new int[height][width];
for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
array_new[y][x] = array[x][y];
}
}
return array_new;
}
private static int[][] swapRows(int[][] m) {
for (int i = 0, k = m.length - 1; i < k; ++i, --k) {
int[] x = m[i];
m[i] = m[k];
m[k] = x;
}
return m;
}
}
Comments
Post a Comment