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:

After peeling top-right layer:

After peeling bottom-left layer from sub-matrix:

After peeling top-right layer from sub-matrix:

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

Print two-dimensional array in spiral order

Solution 1:

Solution 2:

Solution 3:

Related

Recent Posts