Print two-dimensional array in spiral order
Solution 1
The idea is to treat the matrix as a series of layers, top-right layers and bottom-left layers. To print the matrix spirally we can peel layers from these matrix, print the peeled part and recursively call the print on the left over part. The recursion terminates when we don't have any more layers to print.
Input matrix:
1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6
7 8 9 1
After peeling top-right layer:
1 2 3 4
8
5 6 7 2
9 0 1 6
3 4 5 1
7 8 9
After peeling bottom-left layer from sub-matrix:
6 7
5 0 1
9 4 5
3
7 8 9
After peeling top-right layer from sub-matrix:
6 7
1
0 5
4
After peeling bottom-left layer from sub-matrix:
0
4
Recursion terminates.
C functions:
// function to print the top-right peel of the matrix and
// recursively call the print bottom-left on the submatrix.
void printTopRight(int a[][COL], int x1, int y1, int x2, int y2) {
int i = 0, j = 0;
// print values in the row.
for(i = x1; i<=x2; i++) {
printf("%d ", a[y1][i]);
}
// print values in the column.
for(j = y1 + 1; j <= y2; j++) {
printf("%d ", a[j][x2]);
}
// see if more layers need to be printed.
if(x2-x1 > 0) {
// if yes recursively call the function to
// print the bottom left of the sub matrix.
printBottomLeft(a, x1, y1 + 1, x2-1, y2);
}
}
// function to print the bottom-left peel of the matrix and
// recursively call the print top-right on the submatrix.
void printBottomLeft(int a[][COL], int x1, int y1, int x2, int y2) {
int i = 0, j = 0;
// print the values in the row in reverse order.
for(i = x2; i>=x1; i--) {
printf("%d ", a[y2][i]);
}
// print the values in the col in reverse order.
for(j = y2 - 1; j >= y1; j--) {
printf("%d ", a[j][x1]);
}
// see if more layers need to be printed.
if(x2-x1 > 0) {
// if yes recursively call the function to
// print the top right of the sub matrix.
printTopRight(a, x1+1, y1, x2, y2-1);
}
}
void printSpiral(int arr[][COL]) {
printTopRight(arr,0,0,COL-1,ROW-1);
printf("\n");
}
Solution 2
- Pop top row
- Transpose and flip upside-down (same as rotate 90 degrees counter-clockwise)
- Go to 1
Python 2 code:
import itertools
arr = [[1,2,3,4],
[12,13,14,5],
[11,16,15,6],
[10,9,8,7]]
def transpose_and_yield_top(arr):
while arr:
yield arr[0]
arr = list(reversed(zip(*arr[1:])))
print list(itertools.chain(*transpose_and_yield_top(arr)))
For python 3x:
import itertools
arr = [[1,2,3,4],
[12,13,14,5],
[11,16,15,6],
[10,9,8,7]]
def transpose_and_yield_top(arr):
while arr:
yield arr[0]
arr = list(reversed(list(zip(*arr[1:]))))
print(list(itertools.chain(*transpose_and_yield_top(arr))))
Solution 3
I see that no one has use only one for loop and without recursion in the code, and so I want to contribute.
The idea is like this:
Imagine there is a turtle standing at point (0,0), that is, top-left corner, facing east (to the right)
It will keep going forward and each time it sees a sign, the turtle will turn right
So if we put the turtle at point (0,0) facing right-ward, and if we place the signs at appropriate places, the turtle will traverse the array in spiral way.
Now the problem is: "Where to put the signs?"
Let's see where we should put the signs (marked by #, and numbers by O):
For a grid that looks like this: O O O O O O O O O O O O O O O O We put the signs like this: O O O # # O # O O # # O # O O # For a grid that looks like this: O O O O O O O O O O O O We put the signs like this: O O # # # O O # O # O # And for a grid that looks like this: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O We put the signs like this: O O O O O O # # O O O O # O O # O O # O O O # O O O # O # O O O O O #
We can see that, unless the point is at the top-left part, the signs are places at points where the distances to the closest horizontal border and the closest vertical border are the same, while for the top-left part, the distance to the top border is one more than the distance to the left border, with priority given to top-right in case the point is horizontally centered, and to top-left in case the point is vertically centered.
This can be realized in a simple function quite easily, by taking the minimum of (curRow and height-1-curRow), then the minimum of (curCol and width-1-curCol) and compare if they are the same. But we need to account for the upper-left case, that is, when the minimum is curRow and curCol themselves. In that case we reduce the vertical distance accordingly.
Here is the C code:
#include <stdio.h>
int shouldTurn(int row, int col, int height, int width){
int same = 1;
if(row > height-1-row) row = height-1-row, same = 0; // Give precedence to top-left over bottom-left
if(col >= width-1-col) col = width-1-col, same = 0; // Give precedence to top-right over top-left
row -= same; // When the row and col doesn't change, this will reduce row by 1
if(row==col) return 1;
return 0;
}
int directions[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
void printSpiral(int arr[4][4], int height, int width){
int directionIdx=0, i=0;
int curRow=0, curCol=0;
for(i=0; i<height*width; i++){
printf("%d ",arr[curRow][curCol]);
if(shouldTurn(curRow, curCol, height, width)){
directionIdx = (directionIdx+1)%4;
}
curRow += directions[directionIdx][0];
curCol += directions[directionIdx][1];
}
printf("\n");
}
int main(){
int arr[4][4]= {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
printSpiral(arr, 4, 4);
printSpiral(arr, 3, 4);
}
Which outputs:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 1 2 3 4 8 12 11 10 9 5 6 7
Solution 4
Here are the three interesting ways
Reading in spiral way can be treated like a snake moving towards boundary and turning on hitting the boundary or itself (I find it elegant and most efficient being a single loop of N iterations)
ar = [ [ 0, 1, 2, 3, 4], [15, 16, 17, 18, 5], [14, 23, 24, 19, 6], [13, 22, 21, 20, 7], [12, 11, 10, 9, 8]] def print_spiral(ar): """ assuming a rect array """ rows, cols = len(ar), len(ar[0]) r, c = 0, -1 # start here nextturn = stepsx = cols # move so many steps stepsy = rows-1 inc_c, inc_r = 1, 0 # at each step move this much turns = 0 # how many times our snake had turned for i in range(rows*cols): c += inc_c r += inc_r print ar[r][c], if i == nextturn-1: turns += 1 # at each turn reduce how many steps we go next if turns%2==0: nextturn += stepsx stepsy -= 1 else: nextturn += stepsy stepsx -= 1 # change directions inc_c, inc_r = -inc_r, inc_c print_spiral(ar)
output:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
A recursive approach would be to print outer layer and call same function for inner rectangle e.g.
def print_spiral(ar, sr=0, sc=0, er=None, ec=None): er = er or len(ar)-1 ec = ec or len(ar[0])-1 if sr > er or sc > ec: print return # print the outer layer top, bottom, left, right = [], [], [], [] for c in range(sc,ec+1): top.append(ar[sr][c]) if sr != er: bottom.append(ar[er][ec-(c-sc)]) for r in range(sr+1,er): right.append(ar[r][ec]) if ec != sc: left.append(ar[er-(r-sr)][sc]) print " ".join([str(a) for a in top + right + bottom + left]), # peel next layer of onion print_spiral(ar, sr+1, sc+1, er-1, ec-1)
Finally here is a small snippet to do it, not efficient but fun :), basically it prints top row, and rotates whole rectangle anti-clockwise and repeats
def print_spiral(ar):
if not ar: return
print " ".join(str(a) for a in ar[0]),
ar = zip(*[ reversed(row) for row in ar[1:]])
print_spiral(ar)
Solution 5
This program works for any n*n matrix..
public class circ {
public void get_circ_arr (int n,int [][] a)
{
int z=n;
{
for (int i=0;i<n;i++)
{
for (int l=z-1-i;l>=i;l--)
{
int k=i;
System.out.printf("%d",a[k][l]);
}
for (int j=i+1;j<=z-1-i;j++)
{
int k=i;
{
System.out.printf("%d",a[j][k]);
}
}
for (int j=i+1;j<=z-i-1;j++)
{
int k=z-1-i;
{
System.out.printf("%d",a[k][j]);
}
}
for (int j=z-2-i;j>=i+1;j--)
{
int k=z-i-1;
{
System.out.printf("%d",a[j][k]);
}
}
}
}
}
}
Hope it helps
Comments
-
Rahul Vyas almost 4 years
How do I print a 5×5 two-dimensional array in spiral order?
Is there any formula so that I can print an array of any size in spiral order?