Neighbors of a matrix element

Question

I would like a code review to make this code better, clear, and concise.

The problem it's solving is as follows:

Given a matrix, print the circumference of each of the items. For example:

1 2 3 
4 5 6 
7 8 9

should result in

1 : 2 4 5
2 : 1 4 5 6 3
3 : 2 5 6 
etc. 

Also, am I correct in saying the time complexity is O(n⁴)?

public final class PrintCircumference {
 private PrintCircumference() {
 }
 public static void printCircumference(int[][] m) {
 if (m == null) {
 throw new NullPointerException("The input matrix cannot be null");
 }
 int row = m.length;
 int col = m[0].length;
 for (int i = 0; i < row; i++) {
 for (int j = 0; j < col; j++) {
 System.out.print(m[i][j] + " --> ");
 for (int i1 = Math.max(0, i -1); i1 < Math.min(row, i + 2); i1++) {
 for (int j1 = Math.max(0, j -1); j1 < Math.min(col, j + 2); j1++) {
 if (i1 != i || j1 != j)
 System.out.print(m[i1][j1]);
 }
 }
 System.out.println();
 }
 }
 }
 public static void main(String[] args) {
 int[][] m = { {1, 2, 3},
 {4, 5, 6},
 {7, 8, 9}, };
 printCircumference(m);
 }
}

• 200_success: Complexity is O(rows * cols). For each matrix element in question, the two innermost for-loops will iterate through at most 8 neighbors (plus itself), regardless of the matrix size. Since 9 is a constant factor, you can ignore it in the complexity estimate.
• Clockwork-Muse: Actually, the output for 2 is currently 1 3 4 5 6. Do you want it printed in 'counter-clockwise' order, or the current order is fine?
• 200_success: @Clockwork-Muse That depends: are you a digital or analog clockwork muse? If digital, then row-major order, else counter-clockwise order.

Answer 1

Hmm, I think there's two things I'd do:

1. Put the 'neighbors' loops into their own method.
2. Potentially, separating the neighbor collection from the actual printing.

(Please note that I've attempted to format this slightly better for SO's display width)

public final class PrintCircumference {
 private PrintCircumference() {
 }
 public static void printCircumference(int[][] matrix) {
 if (matrix == null) {
 throw new NullPointerException("The input matrix cannot be null");
 }
 for (int currentRow = 0, 
 rowCount = matrix.length, 
 columnCount = matrix[0].length; currentRow < rowCount; currentRow++) {
 for (int currentColumn = 0; currentColumn < columnCount; currentColumn++) {
 System.out.println(matrix[currentRow][currentColumn] 
 + " --> " 
 + collectNeighbors(matrix, rowCount, columnCount, currentRow, currentColumn));
 }
 }
 }
 private static String collectNeighbors(int[][] matrix, int rowCount, int columnCount, int originCellRow, int originCellColumn) {
 StringBuilder neighbors = new StringBuilder();
 for (int neighborRow = Math.max(0, originCellRow - 1), 
 neighborRowLimit = Math.min(rowCount, originCellRow + 2), 
 neighborColumnLimit = Math.min(columnCount, originCellColumn + 2); neighborRow < neighborRowLimit; neighborRow++) {
 for (int neighborColumn = Math.max(0, originCellColumn - 1); neighborColumn < neighborColumnLimit; neighborColumn++) {
 if (neighborRow != originCellRow || neighborColumn != originCellColumn) {
 neighbors.append(matrix[neighborRow][neighborColumn]);
 }
 }
 }
 return neighbors.toString();
 }
 public static void main(String[] args) {
 int[][] m = { { 1, 2, 3 }, 
 { 4, 5, 6 }, 
 { 7, 8, 9 }, };
 printCircumference(m);
 }
}

I've scoped the variables about as tightly as is possible.
Also, the original row and column variables are slightly misnamed - they're the count/limit, whereas most developers are probably expecting them to be the 'current' value. In addition, while i is fine for a single loop, when you're explicitly looping over columns/rows, please name your variables as such. Use new methods to let you 'rename variables in context' (something like what I've done with the currentRow -> originCellRow, etc, here). It's also usually a good idea to put brackets on every loop/condition, in case something more needs to be added at some point in the future.

One word of warning - you're not doing enough error-checking here; fixing that is left as an exercise for the reader (for instance, I was unsure if anything should be printed if the matrix wasn't completely square).

• 200_success: Good, but please resist the urge to assign everything in the for-loop initialization. A for-loop should be about something. For example, in your first loop, the update field is currentRow++, so just write for (int currentRow = 0; currentRow < rowCount; currentRow++). Similarly, for (int neighborRow = Math.max(0, originCellRow - 1); neighborRow < neighborRowLimit; neighborRow++).

Answer 2

If you like to reduce loops in your code, you can do it similar to this one:

static void printDirection(int [][]m, int r1, int r2, int col1, int col2, boolean cond)
{
 System.out.print( m[r1][col1] + " " );
 if (cond) System.out.print( m[r2][col2] + " " );
}
public static void PrintCircumference(int [][] m)
{
 int HEIGHT = m.length;
 int WIDTH = m[0].length;
 for (int iRow = 0;iRow < HEIGHT; ++iRow)
 {
 boolean isRowNotZero = iRow != 0;
 boolean isRowLessHeight_1 = iRow < HEIGHT - 1;
 int iRowPlusOne = iRow + 1;
 int iRowMinusOne = iRow - 1;
 for (int iCol = 0;iCol < WIDTH; ++iCol)
 {
 boolean isColNotZero = iCol != 0;
 boolean isColLessWidth_1 = iCol < WIDTH - 1;
 int iColPlusOne = iCol + 1;
 int iColMinusOne = iCol - 1;
 System.out.print( m[iRow][iCol] + " : " );
 //north
 if (isRowNotZero)
 {
 printDirection(m,
 iRowMinusOne,iRowMinusOne,
 iCol, iColMinusOne,
 isColNotZero);
 }
 //west
 if (isColNotZero)
 {
 printDirection(m,
 iRow,iRowPlusOne,
 iColMinusOne, iColMinusOne,
 isRowLessHeight_1);
 }
 //south
 if (isRowLessHeight_1)
 {
 printDirection(m,
 iRowPlusOne,iRowPlusOne,
 iCol, iColPlusOne,
 isColLessWidth_1);
 }
 //east
 if (isColLessWidth_1)
 {
 printDirection(m,
 iRow,iRowMinusOne,
 iColPlusOne, iColPlusOne,
 isRowNotZero);
 }
 System.out.println();
 }
 System.out.println( "-->" );
 }
}

It checks all neighbors counter-clockwise.

It's working, and tested already :)

Update: Rework the code to be more optimized.

Profiled here

Yours:

Compilation time: 0.73 sec, absolute running time: 0.13 sec, cpu time: 0.09 sec, memory peak: 14 Mb, absolute service time: 0.87 sec (cached)

This one:

Compilation time: 0.74 sec, absolute running time: 0.14 sec, cpu time: 0.06 sec, memory peak: 14 Mb, absolute service time: 0.89 sec

Although a little bit of difference in performance. Still it's up to you. Just a suggestion :)

• Clockwork-Muse: Personally, I'd argue that this is more complex. You have more conditions (and are specifically checking for directions), and the way that you're specifically calling out rows/columns there is more prone to error (ie, flubbing a minus for a plus). Also, the counter-clockwise thing is due to an error/type in the output, and does not match current behavior... Also, I didn't catch this before, but your diagonal checks have a redundant condition in them.
• mr5: @Clockwork-Muse I'm sorry for the wrong term I used. I edited my post. And also, counter-clockwise thing is the sequence w/c they were evaluated, I don't think its an error. It can be rearrange to change the direction.
• Clockwork-Muse: ... that's even worse, frankly. Your variable names are now too cryptic. Additionally, some of the optimizations you're doing are likely to be performed automatically, transparently, by the compiler/JITter.

Answer 3

Ok, my solution is overengineered... I took this as an exercise on State pattern. The good thing here is that you can add different behaviours in different regions of the matrix. Here it is:

package it.test.refactor;
public class MatrixExploring {
 public static void main(String[] args) {
 int[][] m = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
 new MatrixCircunference(m).explore();
 }
}
class MatrixCircunference {
 private int[][] matrix;
 private int matrixColumns;
 private int matrixRows;
 private int currentColumn;
 private int currentRow;
 private MatrixProcessor NORTHWEST;
 private MatrixProcessor NORTH;
 private MatrixProcessor NORTHEAST;
 private MatrixProcessor CENTER;
 private MatrixProcessor WEST;
 private MatrixProcessor EAST;
 private MatrixProcessor SOUTHWEST;
 private MatrixProcessor SOUTH;
 private MatrixProcessor SOUTHEAST;
 private MatrixProcessor processor;
 public MatrixCircunference(int[][] m) {
 if (m == null) {
 throw new NullPointerException("The input matrix cannot be null");
 }
 this.matrix = m;
 currentColumn = 0;
 currentRow = 0;
 matrixRows = m.length;
 matrixColumns = m[0].length;
 System.out.println("Matrix dimensions: " + matrixColumns + " - " + matrixRows);
 if (matrixRows < 3 || matrixColumns < 3) {
 throw new IllegalArgumentException("The input matrix must have at least 3 columns and 3 rows");
 }
 NORTHWEST = new NorthWest();
 NORTH = new North();
 NORTHEAST = new NorthEast();
 CENTER = new Center();
 WEST = new West();
 EAST = new East();
 SOUTHWEST = new SouthWest();
 SOUTH = new South();
 SOUTHEAST = new SouthEast();
 }
 public void explore() {
 processor = NORTHWEST;
 while (processor != null) {
 processor.process();
 processor = processor.nextProcessor();
 }
 }
 interface MatrixProcessor {
 void process();
 MatrixProcessor nextProcessor();
 }
 class NorthWest implements MatrixProcessor {
 public void process() {
 System.out.println(matrix[0][0] + ":\t" + matrix[0][1] + "\t" + matrix[1][0] + "\t" + matrix[1][1]);
 }
 @Override
 public MatrixProcessor nextProcessor() {
 currentColumn = 1;
 return NORTH;
 }
 }
 class North implements MatrixProcessor {
 @Override
 public void process() {
 System.out.println(matrix[0][currentColumn] + ":\t" + matrix[0][currentColumn - 1] + "\t"
 + matrix[0][currentColumn + 1] + "\t" + matrix[1][currentColumn - 1] + "\t"
 + matrix[1][currentColumn] + "\t" + matrix[1][currentColumn + 1] + "\t");
 }
 @Override
 public MatrixProcessor nextProcessor() {
 currentColumn++;
 if (matrixColumns > currentColumn + 1) {
 return this;
 }
 return NORTHEAST;
 }
 }
 class NorthEast implements MatrixProcessor {
 @Override
 public void process() {
 System.out.println(matrix[0][currentColumn] + ":\t" + matrix[0][currentColumn - 1] + "\t"
 + matrix[1][currentColumn - 1] + "\t" + matrix[1][currentColumn] + "\t");
 }
 @Override
 public MatrixProcessor nextProcessor() {
 currentColumn = 0;
 currentRow = 1;
 return WEST;
 }
 }
 class West implements MatrixProcessor {
 @Override
 public void process() {
 System.out.println(matrix[currentRow][currentColumn] + ":\t" + matrix[currentRow - 1][currentColumn] + "\t"
 + matrix[currentRow - 1][currentColumn + 1] + "\t"
 + matrix[currentRow][currentColumn + 1] + "\t" + matrix[currentRow + 1][currentColumn]
 + "\t" + matrix[currentRow + 1][currentColumn + 1] + "\t");
 }
 @Override
 public MatrixProcessor nextProcessor() {
 currentColumn = 1;
 return CENTER;
 }
 }
 class Center implements MatrixProcessor {
 @Override
 public void process() {
 System.out.println(matrix[currentRow][currentColumn] + ":\t" + matrix[currentRow - 1][currentColumn - 1]
 + "\t" + matrix[currentRow - 1][currentColumn] + "\t"
 + matrix[currentRow - 1][currentColumn + 1] + "\t"
 + matrix[currentRow][currentColumn - 1] + "\t" + matrix[currentRow][currentColumn + 1]
 + "\t" + matrix[currentRow + 1][currentColumn - 1] + "\t"
 + matrix[currentRow + 1][currentColumn] + "\t"
 + matrix[currentRow + 1][currentColumn + 1] + "\t");
 }
 @Override
 public MatrixProcessor nextProcessor() {
 currentColumn++;
 if (matrixColumns > currentColumn + 1) {
 return this;
 }
 return EAST;
 }
 }
 class East implements MatrixProcessor {
 @Override
 public void process() {
 System.out.println(matrix[currentRow][currentColumn] + ":\t" + matrix[currentRow - 1][currentColumn - 1]
 + "\t" + matrix[currentRow - 1][currentColumn] + "\t"
 + +matrix[currentRow][currentColumn - 1] + "\t" + "\t"
 + matrix[currentRow + 1][currentColumn - 1] + "\t"
 + matrix[currentRow + 1][currentColumn] + "\t");
 }
 @Override
 public MatrixProcessor nextProcessor() {
 currentColumn = 0;
 currentRow++;
 if (matrixRows > currentRow + 1) {
 return WEST;
 }
 return SOUTHWEST;
 }
 }
 class SouthWest implements MatrixProcessor {
 @Override
 public void process() {
 System.out.println(matrix[currentRow][currentColumn] + ":\t" + matrix[currentRow - 1][currentColumn] + "\t"
 + matrix[currentRow - 1][currentColumn + 1] + "\t"
 + matrix[currentRow][currentColumn + 1] + "\t");
 }
 @Override
 public MatrixProcessor nextProcessor() {
 currentColumn = 1;
 return SOUTH;
 }
 }
 class South implements MatrixProcessor {
 @Override
 public void process() {
 System.out.println(matrix[currentRow][currentColumn] + ":\t" + matrix[currentRow - 1][currentColumn - 1]
 + "\t" + matrix[currentRow - 1][currentColumn] + "\t"
 + matrix[currentRow - 1][currentColumn + 1] + "\t"
 + matrix[currentRow][currentColumn - 1] + "\t" + matrix[currentRow][currentColumn + 1]);
 }
 @Override
 public MatrixProcessor nextProcessor() {
 currentColumn++;
 if (matrixColumns > currentColumn + 1) {
 return this;
 }
 return SOUTHEAST;
 }
 }
 class SouthEast implements MatrixProcessor {
 @Override
 public void process() {
 System.out.println(matrix[currentRow][currentColumn] + ":\t" + matrix[currentRow - 1][currentColumn - 1]
 + "\t" + matrix[currentRow - 1][currentColumn] + "\t"
 + matrix[currentRow][currentColumn - 1] + "\t");
 }
 @Override
 public MatrixProcessor nextProcessor() {
 return null;
 }
 }
}