Spiral Matrix

I ran into this challenge described in C/C++ as follows:

#define MATRIX_SIZE 3

#if MATRIX_SIZE == 3

int matrix[3][3] = {

    { 11, 12, 13 },

    { 21, 22, 23 },

    { 31, 32, 33 }

};

#elif MATRIX_SIZE == 4

int matrix[4][4] = {

{ 11, 12, 13, 14 },

{ 21, 22, 23, 24 },

{ 31, 32, 33, 34 },

{ 41, 42, 43, 44 }

};

#else

int matrix[6][6] = {

{ 11, 12, 13, 14, 15, 16 },

{ 21, 22, 23, 24, 25, 26 },

{ 31, 32, 33, 34, 35, 36 },

{ 41, 42, 43, 44, 45, 46 },

{ 51, 52, 53, 54, 55, 56 },

{ 61, 62, 63, 64, 65, 66 }

};

#endif

Given a rectangular matrix of integers [editorial: could be any type of data if one uses generics; I will skip that part] display the values in a spiral fashion. For example, the first matrix[3][3] would produce:  11 12 13 23 33 32 31 11 22.

I decided to generate a solution using Java. The only difference is that the constant MATRIX_SIZE would not be needed.

I generated the following test code:

/**

* Test code

*/

public static void main(String[] args) {

// **** first test ****

int[][] matrixA = new int[][]     {

{ 11, 12, 13 },

{ 21, 22, 23 },

{ 31, 32, 33 }

};

// **** second test ****

int[][] matrixB = new int[][]     {

{ 11, 12, 13, 14 },

{ 21, 22, 23, 24 },

{ 31, 32, 33, 34 },

{ 41, 42, 43, 44 }

};

// **** third test ****

int[][] matrixC = new int[][]     {

{ 11, 12, 13, 14, 15, 16 },

{ 21, 22, 23, 24, 25, 26 },

{ 31, 32, 33, 34, 35, 36 },

{ 41, 42, 43, 44, 45, 46 },

{ 51, 52, 53, 54, 55, 56 },

{ 61, 62, 63, 64, 65, 66 }

};

// **** ****

for (int i = 0; i < 3; i++) {

// **** for the looks ****

System.out.println(“matrix: “);

// **** ****

if (i == 0)

spiralPrint(matrixA);

else if (i == 1)

spiralPrint(matrixB);

else

spiralPrint(matrixC);

 

// **** for the looks ****

 

System.out.println();

}

}

I have this habit to always generate test code first (TDD). It will obviously fail. Then move into the solution. It is all about repeating the architecture, design, coding and testing SDLC.

The actual solution follows:

/**

* Print the contents of a border in spiral order.

*/

static void displayBorder(int[][]matrix, int offset) {

// **** ****

int begin     = offset;

int end       = (matrix.length – 1) – offset;

int col = 0;

int row = 0;

// **** display top row ****

row = begin;

for (col = begin; col < end; col++) {

System.out.print(matrix[row][col] + ” “);

}

// **** display right column ***

col = end;

for (row = begin; row < end; row++) {

System.out.print(matrix[row][col] + ” “);

}

// **** display bottom row ****

row = end;

for (col = end; col > begin; col–) {

System.out.print(matrix[row][col] + ” “);

}

// **** display left column ****

col = begin;

for (row = end; row > begin; row–) {

System.out.print(matrix[row][col] + ” “);

}

}

/**

* Print the contents of the matrix in a spiral.

*/

static void spiralPrint(int[][] matrix) {

// **** display the initial matrix ****

for (int row = 0; row < matrix.length; row++) {

for (int col = 0; col < matrix.length; col++) {

System.out.print(matrix[row][col] + ” “);

}

System.out.println();

}

// **** for the looks ****

System.out.println(“spiral: “);

// **** display the values in spiral order ****

for (int offset = 0; offset < (matrix.length / 2) ; offset++) {

displayBorder(matrix, offset);

}

// **** display the last element (if needed) ****

if ((matrix.length % 2) == 1) {

System.out.print(matrix[matrix.length / 2][matrix.length / 2] + ” “);

}

// **** for the looks ****

System.out.println();

}

I decided to tackle the problem one step at a time. From the start, it looked like a matrix with odd or even number of elements per side would have a special case.

The first step was to generate the complete spiral by decrementing the offset each time. The end condition became apparent and was addressed with a special case. That was the second step. The final one was to implement the displayBorder() method. In retrospect I believe it should have been named something else like printPerimeter(). I was lazy not to change it in the actual code.

Following is a screen capture of the console for the Eclipse IDE:

matrix:

11 12 13

21 22 23

31 32 33

spiral:

11 12 13 23 33 32 31 21 22

matrix:

11 12 13 14

21 22 23 24

31 32 33 34

41 42 43 44

spiral:

11 12 13 14 24 34 44 43 42 41 31 21 22 23 33 32

matrix:

11 12 13 14 15 16

21 22 23 24 25 26

31 32 33 34 35 36

41 42 43 44 45 46

51 52 53 54 55 56

61 62 63 64 65 66

spiral:

11 12 13 14 15 16 26 36 46 56 66 65 64 63 62 61 51 41 31 21 22 23 24 25 35 45 55 54 53 52 42 32 33 34 44 43

For ease I display the actual matrix followed by the contents displayed in spiral.

If you have comments or questions regarding this or any other post in this blog, please do not hesitate and send me a message. I will reply as soon as possible and will not use your name unless you explicitly allow me to do so.

John

john.canessa@gmail.com

Follow me on Twitter:   @john_canessa

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.