Print two-dimensional array in spiral order

Question

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?

Answer 1

Complexity: Single traverse O(n)

Please let me add my single loop answer with complexity O(n). I have observed that during left-right and right-left traverse of the matrix, there is an increase and decrease by one respectively in the row-major index. Similarly, for the top-bottom and bottom-top traverse there is increase and decrease by n_cols. Thus I made an algorithm for that. For example, given a (3x5) matrix with entries the row-major indexes the print output is: 1,2,3,4,5,10,15,14,13,12,11,6,7,8,9.

             ------->(+1)
          ^ 1  2  3  4  5   |
(+n_cols) | 6  7  8  9  10  | (-n_cols)
          | 11 12 13 14 15  
            (-1)<-------

Code solution:

#include <iostream>
using namespace std;

int main() {
    // your code goes here

    bool leftToRight=true, topToBottom=false, rightToLeft=false, bottomToTop=false;
    int idx=0;
    int n_rows = 3;
    int n_cols = 5;
    int cnt_h = n_cols, cnt_v = n_rows, cnt=0;
    int iter=1;
    for (int i=0; i <= n_rows*n_cols + (n_rows - 1)*(n_cols - 1)/2; i++){

        iter++; 
        if(leftToRight){
            if(cnt >= cnt_h){ 
                cnt_h--; cnt=0;
                leftToRight = false; topToBottom = true; 
                //cout  << "Iter: "<< iter << " break_leftToRight"<<endl;
            }else{
                cnt++;
                idx++;
                //cout << "Iter: "<< iter <<" idx: " << idx << " cnt: "<< cnt << " cnt_h: "<< cnt_h<< endl;
                cout<< idx << endl;
            }
        }else if(topToBottom){
            if(cnt >= cnt_v-1){
                cnt_v--; cnt=0;  
                leftToRight = false; topToBottom = false; rightToLeft=true;
                //cout  << "Iter: "<< iter  << " break_topToBottom"<<endl;
            }else{
                cnt++;
                idx+=n_cols;
                //cout  << "Iter: "<< iter << " idx: " << idx << " cnt: "<< cnt << " cnt_v: "<< cnt_h<< endl;
                cout << idx <<endl;
            }
        }else if(rightToLeft){
            if(cnt >= cnt_h){
                cnt_h--; cnt=0; 
                leftToRight = false; topToBottom = false; rightToLeft=false; bottomToTop=true;
                //cout  << "Iter: "<< iter  << " break_rightToLeft"<<endl;
                //cout<< idx << endl;
            }else{
                cnt++;
                idx--;
                //cout  << "Iter: "<< iter << " idx: " << idx << " cnt: "<< cnt << " cnt_h: "<< cnt_h<< endl;
                cout << idx <<endl;
            }
        }else if(bottomToTop){
            if(cnt >= cnt_v-1){
                cnt_v--; cnt=0;
                leftToRight = true; topToBottom = false; rightToLeft=false; bottomToTop=false;
                //cout  << "Iter: "<< iter << " break_bottomToTop"<<endl;
            }else{
                cnt++;
                idx-=n_cols;
                //cout  << "Iter: "<< iter << " idx: " << idx << " cnt: "<< cnt << " cnt_v: "<< cnt_h<< endl;
                cout<< idx << endl;
            }
        }

        //cout << i << endl;
    }


    return 0;
}

Answer 2

Given a matrix of chars, implement a method that prints all characters in the following order: first the outer circle, then the next one and so on.

public static void printMatrixInSpiral(int[][] mat){

    if(mat.length == 0|| mat[0].length == 0){
        /* empty matrix */
        return;
    }

    StringBuffer str = new StringBuffer();
    int counter = mat.length * mat[0].length;
    int startRow = 0;
    int endRow = mat.length-1;
    int startCol = 0;
    int endCol = mat[0].length-1;
    boolean moveCol = true;
    boolean leftToRight = true;
    boolean upDown = true;

    while(counter>0){

        if(moveCol){

            if(leftToRight){

                /* printing entire row left to right */                 
                for(int i = startCol; i <= endCol ; i++){                       
                    str.append(mat[startRow][i]);
                    counter--;
                }
                leftToRight = false;
                moveCol = false;
                startRow++;
            }
            else{

                /* printing entire row right to left */
                for(int i = endCol ; i >= startCol ; i--){
                    str.append(mat[endRow][i]);
                    counter--;
                }
                leftToRight = true;
                moveCol = false;
                endRow--;       
            }
        }
        else
        {
            if(upDown){                 

                /* printing column up down */
                for(int i = startRow ; i <= endRow ; i++){                      
                    str.append(mat[i][endCol]);
                    counter--;
                }
                upDown = false;
                moveCol = true;
                endCol--;
            }
            else
            {

                /* printing entire col down up */
                for(int i = endRow ; i >= startRow ; i--){
                    str.append(mat[i][startCol]);
                    counter--;
                }
                upDown = true;
                moveCol = true;
                startCol++;
            }
        }
    }
    System.out.println(str.toString());
}

Answer 3

Here's my approach using an Iterator . Note this solves almost the same problem.. Complete code here : https://github.com/rdsr/algorithms/blob/master/src/jvm/misc/FillMatrix.java

import java.util.Iterator;

class Pair {
    final int i;
    final int j;

    Pair(int i, int j) {
        this.i = i;
        this.j = j;
    }

    @Override
    public String toString() {
        return "Pair [i=" + i + ", j=" + j + "]";
    }
}


enum Direction {
    N, E, S, W;
}


class SpiralIterator implements Iterator<Pair> {
    private final int r, c;
    int ri, ci;
    int cnt;

    Direction d; // current direction
    int level; // spiral level;

    public SpiralIterator(int r, int c) {
        this.r = r;
        this.c = c;

        d = Direction.E;
        level = 1;
    }

    @Override
    public boolean hasNext() {
        return cnt < r * c;
    }

    @Override
    public Pair next() {
        final Pair p = new Pair(ri, ci);
        switch (d) {
            case E:
                if (ci == c - level) {
                    ri += 1;
                    d = changeDirection(d);
                } else {
                    ci += 1;
                }
                break;

            case S:
                if (ri == r - level) {
                    ci -= 1;
                    d = changeDirection(d);
                } else {
                    ri += 1;
                }
                break;

            case W:
                if (ci == level - 1) {
                    ri -= 1;
                    d = changeDirection(d);
                } else {
                    ci -= 1;
                }
                break;

            case N:
                if (ri == level) {
                    ci += 1;
                    level += 1;
                    d = changeDirection(d);
                } else {
                    ri -= 1;
                }
                break;
        }

        cnt += 1;
        return p;
    }

    private static Direction changeDirection(Direction d) {
        switch (d) {
            case E:
                return Direction.S;
            case S:
                return Direction.W;
            case W:
                return Direction.N;
            case N:
                return Direction.E;
            default:
                throw new IllegalStateException();
        }
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

}


public class FillMatrix {
    static int[][] fill(int r, int c) {
        final int[][] m = new int[r][c];
        int i = 1;
        final Iterator<Pair> iter = new SpiralIterator(r, c);
        while (iter.hasNext()) {
            final Pair p = iter.next();
            m[p.i][p.j] = i;
            i += 1;
        }
        return m;
    }

    public static void main(String[] args) {
        final int r = 19, c = 19;
        final int[][] m = FillMatrix.fill(r, c);
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                System.out.print(m[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Answer 4

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

Answer 5

This is my implementation:

public static void printMatrix(int matrix[][], int M, int N){
    int level = 0;
    int min = (M < N) ? M:N;
    System.out.println();
    while(level <= min/2){
        for(int j = level; j < N - level - 1; j++){
            System.out.print(matrix[level][j] + "\t");
        }
        for(int i = level; i < M - level - 1; i++) {
            System.out.print(matrix[i][N - level - 1] + "\t");
        }
        for(int j = N - level - 1; j > level; j--){
            System.out.print(matrix[M - level - 1][j] + "\t");
        }
        for(int i = M - level - 1; i > level; i-- ){
            System.out.print(matrix[i][level] + "\t");
        }
        level++;
    }
}

Answer 6

For printing a 2-D matrix consider matrix as a composition of rectangles and/or line where smaller rectangle is fitted into larger one, take boundary of matrix which forms a rectangle to be printed, starting with up-left element each time in each layer; once done with this go inside for next layer of smaller rectangle, in case i don't have a rectangle then it should be line to be printed, a horizontal or vertical. I have pasted the code with an example matrix, HTH.

#include <stdio.h>

int a[2][4] = { 1, 2 ,3, 44,
                8, 9 ,4, 55 };

void print(int, int, int, int);

int main() {

int row1, col1, row2, col2;

row1=0;
col1=0;
row2=1;
col2=3;


while(row2>=row1 && col2>=col1)
{
    print(row1, col1, row2, col2);

    row1++;
    col1++;
    row2--;
    col2--;
}

return 0;
}


void print(int row1, int col1, int row2, int col2) {

int i=row1;
int j=col1;

/* This is when single horizontal line needs to be printed */
if( row1==row2 && col1!=col2) {
    for(j=col1; j<=col2; j++)
        printf("%d ", a[i][j]);
    return;
}

/* This is when single vertical line needs to be printed */
if( col1==col2 && row1!=row2) {
    for(i=row1; j<=row2; i++)
        printf("%d ", a[i][j]);
    return;
}


/* This is reached when there is a rectangle to be printed */

for(j=col1; j<=col2; j++)
    printf("%d ", a[i][j]);

for(j=col2,i=row1+1; i<=row2; i++)
    printf("%d ", a[i][j]);

for(i=row2,j=col2-1; j>=col1; j--)
    printf("%d ", a[i][j]);

for(j=col1,i=row2-1; i>row1; i--)
    printf("%d ", a[i][j]);

}