How do I change the directions and starting points of this matrix spiral traversal?

Question

I have some code (following this example) to traverse a matrix starting from the upper left and going clockwise. I want to make three new methods based off of this:

One that starts from the top left and goes counterclockwise
One that starts from the middle and goes clockwise
One that starts from the middle and goes counterclockwise

What do I need to change for each of these to work? I've tried reversing the counter increments and changing the start/end row/columns with no success.

public static void traverseSpiral(int[][] matrix) {

    if(matrix.length == 0|| matrix[0].length == 0) {
        return;
    }

    StringBuffer stringBuffer = new StringBuffer();
    int counter = matrix.length * matrix[0].length;
    int startRow = 0;
    int endRow = matrix.length-1;
    int startCol = 0;
    int endCol = matrix[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++){
                    stringBuffer.append(matrix[startRow][i]);
                    counter--;
                }
                leftToRight = false;
                moveCol = false;
                startRow++;
            }
            else{

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

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

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

It's not, I assure you. I was looking around for SE intern interview questions and the topic of spiral traversals came up, so I wanted to play around with it. — Chelsea Kelly-Reif, Jan 14 '14 at 09:30
Have any of the answers here helped you? If so, please consider marking this question answered. — Taylor Hx, Jan 20 '14 at 05:51

score 2 · Accepted Answer · edited May 23 '17 at 12:29

The problem with your code is that you dumped it all into one method, making your code very difficult to read and more difficult to modify (without breaking anything).

Since this is for an interview question, you should be striving to not just find the solution, but finding the most elegant solution. Or the fastest solution. Or the shortest. Ultimately, every programmer has different priorities when it comes to code. But most (if not all programmers) strive to write good code.

Good code is easy to read, write and maintain. Although there is no exact definition of what makes good code, Kristopher Johnson posted this answer which I feel does a good job of covering the essentials.

Consider breaking your code up into individual methods, each with their own responsibility. Right away, I can see four code blocks that should be their own methods (printing left to right, right to left, top to bottom and bottom to top). This will make your code much cleaner.

For example, in a recursive solution to this problem, I would have at least 5 methods:

// A method that will handle the traversal of the spiral.
public static String clockwise(int[][] matrix);

// Responsible for printing a column from bottom to top.
public static String up(int[][] matrix, int first, int last);

// Responsible for printing a column from top to bottom.
public static String down(int[][] matrix, int first, int last);

// Responsible for printing a column from right to left.
public static String left(int[][] matrix, int first, int last);

// Responsible for printing a column from left to right.
public static String right(int[][] matrix, int first, int last);

With methods like those, implementing a method to traverse the same spiral counter-clockwise would be a simple as writing another method that reuses code from up(matrix, first, last), down(matrix, first, last), left(matrix, first, last) & right(matrix, first, last) since:

Clockwise          = right, down, left, up;
Counter-Clockwise  = down, right, up, left;

Personally, I prefer a divide-and-conquer recursive approach. Since spiralling around a grid of size 3x3 is essentially the same as spiralling around a grid of 2x2 with one extra lap, you can use recursion to find & solve the smallest version of your problem and build up in steps to your solution.

I'd strongly recommend that you look into recursion and the divide & conquer approach independently. If you're just interested in a solution to your spiral traversal problem, including clockwise, counter-clockwise, clockwise outwards and counter-clockwise outwards, see the GitHub Gist here.

Note: The code above is provided as-is, without any guarantees of any kind. So be warned.

score 1 · Answer 2 · answered Jan 17 '14 at 08:48

There's three methods needed to be implements:

One that starts from the top left and goes counterclockwise
One that starts from the middle and goes clockwise
One that starts from the middle and goes counterclockwise

Let's talk about the first one (that you implemented it)

Let's take a 3x3 matrix

+---+---+---+  
|   |   |   |
+---+---+---+  
|   |   |   |
+---+---+---+  
|   |   |   |
+---+---+---+

So with your implementation, it should be

SR=0, ER=2, SC=0, EC=2

(SR: startRow, ER: endRow, SC: startCol, EC: endCol)

SC->EC 
SR++   (=>SR=1)
SR->ER 
EC--   (=>EC=1)
EC->SC 
ER--   (=>ER=1)
ER->SR
SC++   (=>SC=1)
SC->EC
-> finish with (SR=1,ER=1,SC=1,EC=1)

Let's reverse it, so it become the 3rd one.

SR=1, ER=1, SC=1, EC=1
EC->SC
SC--
SR->ER
ER++
SC->EC
EC++
ER->SR
SR--
EC->SC
-> finish with (SR=0,ER=2,SC=0,EC=2)

So the point is not only change the values of SR, ER, SC, EC but also change where to modify its value. And everything is reversed, so going left right which is to print startCol becomes to print endCol. Same for other directions.

Therefore,

if(leftToRight) {

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

becomes

if (leftToRight) {

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

Matrix which its row# and column# are odd number, you can choose any starting direction defined by (moveCol, leftRight, upDown). However, matrix which its either row# or column# is even, then starting direction is significant.

+---+---+---+---+  
|   |   |   |   |
+---+---+---+---+  
|   | P |   |   |
+---+---+---+---+  
|   |   |   |   |
+---+---+---+---+  
|   |   |   |   |
+---+---+---+---+

For examples, with a 4x4 matrix, if starting point is P(1,1) (startRow = (4-1)/2, startCol = (4-1)/2), there's only one way to go spiral counter clockwise (upDown = true, leftRight =true, moveCol=false)

A similar way could be applied to the 2nd problem

if (leftToRight) {

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

score 0 · Answer 3 · answered Jan 18 '14 at 01:41

This is quite simple, see my solutions below:

class Region  {
    int left, right, top, bottom;
    Region(int _left, int _right, int _top, int_bottom) {
        left=_left;  right=_right;  top=_top;  bottom=_bottom; 
    }
    boolean isEmpty() { return (left>right || top>bottom); }
    boolean isSingleElement() { return (left==right && top==bottom); }
}

List<Coordinate> traverseClockWise(Region r) {
    List<Coordinate> l = new List<Coordinate>();
    if (r.isEmpty()) {
        return l; 
    }
    if (r.isSingleElement()) {
        l.add(new Coordinate(r.left, r.top));
        return l; 
    }

    for (int i=r.left; i<r.right; i++) {
        l.add(new Coordinate(i, r.top));
    }
    for (int i=r.top; i<r.bottom; i++) {
        l.add(new Coordinate(r.right, i));
    }
    for (int i=r.right; i>r.left; i--) {
        l.add(new Coordinate(i, r.bottom));
    }
    for (int i=r.bottom; i>r.top; i--) {
        l.add(new Coordinate(r.left, i));
    }

    l.addAll(traverseClockWise(new Region(r.left+1, r.right-1, r.top+1, rs.bottom-1)));
    return l;
}


void traverse(Matrix A, int row, int col)  {
}

void example() {
    //suppose A is the matrix you are given and n is the size of the matrix
    Matrix A = new Matrix(n,n);
    List<Coordinates> l = traverseClockWise(new Region(1, n, 1, n));

    // to traverse it from top left counterclockwise
    for (int i=0; i<l.size(); i++) {
        traverse(A, l[i].col, l[i].row);
    }

    // to traverse it from the middle and clockwise
    for (int i=l.size()-1; i>=0; i--) {
        traverse(A, l[i].col, l[i].row);
    }

    // to traverse it from the middle and counterclockwise
    for (int i=l.size()-1; i>=0; i--) {
        traverse(A, l[i].row, l[i].col);
    }
}

How do I change the directions and starting points of this matrix spiral traversal?

3 Answers3