$\large\color{red}\tau$
Given an 2D $m \times n$ array, print out the elements in spiral shape
e.g. \[ \begin{bmatrix} 1 & 2 & 3 & 4\\ 4 & 5 & 6 & 21\\ 7 & 8 & 9 & 11\\ \end{bmatrix} \] Output: [1 2 3 4 21 11 9 8 7 4 5 6]
1. If the 2D array is square matrix, then the algorithm is a bit easier
In fact, the probem is similar to [Rotate square matrix in counterclockwise 90 degrees]
but we assume $m \neq n$
e.g. \[ \begin{bmatrix} 1 & 2 & 3 & 4\\ 4 & 5 & 6 & 21\\ 7 & 8 & 9 & 11\\ \end{bmatrix} \] Output: [1 2 3 4 21 11 9 8 7 4 5 6]
1. If the 2D array is square matrix, then the algorithm is a bit easier
In fact, the probem is similar to [Rotate square matrix in counterclockwise 90 degrees]
but we assume $m \neq n$
There are two special cases that you need to pay attention to
1. when $ m \gt n$
$n$ will be decreased to 0 or 1 first
if $n == 1$
we just can print the inner vertical column
1. when $ m \gt n$
$n$ will be decreased to 0 or 1 first
if $n == 1$
we just can print the inner vertical column
2. when $ m \lt n$
$m$ will be decreased to 0 or 1 first
if $m == 1$
we just can print the inner horizontal row
$m$ will be decreased to 0 or 1 first
if $m == 1$
we just can print the inner horizontal row
From the pictures, we can try to come up a skeleton algorithm
1. we need to walk
From left to right [1, 2, 3]
From top to bottom [4, 21]
From right to left [11, 9, 8]
From bottom to top [7, 4]
From left to right [5, 6]
In two dimensions array, the first index is moving vertically, and the second index is moving horizontally.
1. we need to walk
From left to right [1, 2, 3]
From top to bottom [4, 21]
From right to left [11, 9, 8]
From bottom to top [7, 4]
From left to right [5, 6]
In two dimensions array, the first index is moving vertically, and the second index is moving horizontally.
int array[height][width];
for(int k=0; k < height; k++) {
for(int w=k; w < width-1-k; w++)
array[k][w] // left to right
for(int h=k; h < height-1-k; h++)
array[h][width - 1 - k] // top to bottom
for(int w=k; w < width-1-k; w++)
array[width-1-w][height - 1 - k] // right to left
for(int h=k; h < height-1-k; h++)
array[height - 1 -h][k] // bottom to top
}
// [1, 2]
//
// [1]
//
// [1, 2]
// [3, 4]
//
// [1, 2, 3]
// [4, 5, 6]
// print spiral shape from rectangle
//
public static void rotateRectangle(int[][] arr){
if(arr != null){
int height = arr.length;
if(height > 0){
int width = arr[0].length;
int k = 0;
while(k < Math.min(height, width)){
if(width - 2*k == 1){
for(int i=k; i<height-k; i++){
Print.p(arr[i][k]);
}
break;
}else if(height- 2*k == 1){
for(int i=k; i<width-k; i++){
Print.p(arr[k][i]);
}
break;
}
else if((width - 2*k == 0) || (height - 2*k == 0)){
break;
}else{
for(int i=k; i<width-1-k; i++){
Print.p(arr[k][i]);
}
for(int i=k; i<height-1-k; i++){
Print.p(arr[i][width-1-k]);
}
for(int i=k; i<width-1-k; i++){
Print.p(arr[height-1-k][width-1-i]);
}
for(int i=k; i<height-1-k; i++){
Print.p(arr[height-1-i][k]);
}
}
k++;
}
}
}
}
//
// [1]
// [1, 2]
// [3, 4]
// [0][0] = 1
// [0][1] = 2
// [1][1] = 4
// [1][0] = 3
// k = 1
//
//
// [1, 2, 3]
// [4, 5, 6]
// [7, 8, 9]
// [1, 2] [3, 6] [9, 8] [7, 4]
// [5]
//
// last update
// Tue Sep 27 02:24:44 PDT 2016
// best working version
public static void spiral2(int[][] arr, int k){
if(arr != null && arr.length > 0){
int h = arr.length;
int w = arr[0].length;
if(h - 2*k == 1){
for(int i=k; i<w-k; i++){
Print.p(arr[k][i]);
}
}else if(w - 2*k == 1){
for(int i=k; i<h-k; i++){
Print.p(arr[i][k]);
}
}else if(k < Math.min(h, w)/2){
for(int i=k; i<w-1-k; i++){
Print.p(arr[k][i]);
}
for(int i=k; i<h-1-k; i++){
Print.p(arr[i][w-1-k]);
}
for(int i=k; i<w-1-k; i++){
Print.p(arr[h-1-k][w-1-i]);
}
for(int i=k; i<h-1-k; i++){
Print.p(arr[h-1-i][k]);
}
spiral2(arr, k+1);
}
}
}