Clockwise and counterclockwise spiral matrix traversal

Question

An interviewer asked me to write clean Java code for clockwise and counterclockwise spiral matrix traversal.

e.g. {{1,2,3}, {7,8,9}} becomes {1,2,3,9,8,7} and {1,7,8,9,3,2}

I've tried many methods and wrote down the below code while keeping in mind that it should be as clean as possible. But I am not sure it is the right answer. Please evaluate it.

Note: I've removed comments and test cases to reduce text size.

public abstract class MatrixTraverse {
    private TraverseDirection traverseDirection;
    private int matrixCount;
    private int row;
    private int upLimit;
    private int col;
    private int downLimit;
    private int leftLimit;
    private int rightLimit;
    public abstract void traverseUp();
    public abstract void traverseLeft();
    public abstract void traverseDown();
    public abstract void traverseRight();
    public MatrixTraverse(final TraverseDirection traverseDirection) {
        this.traverseDirection = traverseDirection;
    }
    public void init(int[][] matrix) {
        final int rowSize = matrix.length;
        final int colSize = matrix[0].length;
        upLimit = 0;
        downLimit = matrix.length - 1;
        leftLimit = 0;
        rightLimit = matrix[0].length - 1;
        matrixCount = rowSize * colSize;
        row = 0;
        col = 0;
    }
    public int[] traverseMatrix(int[][] matrix) {
        init(matrix);
        final int[] retTraveserdMatrix = new int[matrixCount];
        for (int index = 0; index < matrixCount; index++) {
            retTraveserdMatrix[index] = matrix[row][col];
            switch (traverseDirection) {
                case RIGHT :
                    traverseRight();
                    break;
                case DOWN :
                    traverseDown();
                    break;
                case LEFT :
                    traverseLeft();
                    break;
                case UP :
                    traverseUp();
                    break;
                default :
                    break;
            }
        }
        return retTraveserdMatrix;
    }
    protected void moveDown() {
        traverseDirection = TraverseDirection.DOWN;
    }
    public void moveRight() {
        traverseDirection = TraverseDirection.RIGHT;
    }
    protected void moveLeft() {
        traverseDirection = TraverseDirection.LEFT;
    }
    protected void moveUp() {
        traverseDirection = TraverseDirection.UP;
    }
    public void decrementRow() {
        --row;
    }
    public boolean isUpLimitExceed() {
        return (row < upLimit);
    }
    public void incrementLeftLimit() {
        ++leftLimit;
    }
    public void incrementCol() {
        ++col;

    }
    public void incrementRow() {
        ++row;
    }
    public boolean isLeftLimitExceed() {
        return (col < leftLimit);
    }
    public void decrementCol() {
        --col;
    }
    public void decrementDownLimit() {
        --downLimit;
    }
    public void decrementRightLimit() {
        --rightLimit;
    }
    public boolean isDownLimitExceed() {
        return (row > downLimit);
    }
    public boolean isRightLimitExceed() {
        return (col > rightLimit);
    }

    public void incrementUpLimit() {
        ++upLimit;
    }
}

public class MatrixTraverseClock extends MatrixTraverse {
    public MatrixTraverseClock() {
        super(TraverseDirection.RIGHT);
    }
    public void traverseUp() {
        decrementRow();
        if (isUpLimitExceed()) {
            incrementRow();
            incrementCol();
            incrementLeftLimit();
            moveRight();
        }
    }
    public void traverseLeft() {
        decrementCol();
        if (isLeftLimitExceed()) {
            incrementCol();
            decrementRow();
            decrementDownLimit();
            moveUp();
        }
    }
    public void traverseDown() {
        incrementRow();
        if (isDownLimitExceed()) {
            decrementRow();
            decrementCol();
            decrementRightLimit();
            moveLeft();
        }
    }
    public void traverseRight() {
        incrementCol();
        if (isRightLimitExceed()) {
            decrementCol();
            incrementRow();
            incrementUpLimit();
            moveDown();
        }
    }
}

public class MatrixTraverseCounterClock extends MatrixTraverse {
    public MatrixTraverseCounterClock() {
        super(TraverseDirection.DOWN);
    }
    public void traverseUp() {
        decrementRow();
        if (isUpLimitExceed()) {
            incrementRow();
            decrementCol();
            decrementRightLimit();
            moveLeft();
        }
    }
    public void traverseLeft() {
        decrementCol();
        if (isLeftLimitExceed()) {
            incrementCol();
            incrementRow();
            incrementUpLimit();
            moveDown();
        }
    }
    public void traverseDown() {
        incrementRow();
        if (isDownLimitExceed()) {
            decrementRow();
            incrementCol();
            incrementLeftLimit();
            moveRight();

        }
    }
    public void traverseRight() {
        incrementCol();
        if (isRightLimitExceed()) {
            decrementCol();
            decrementRow();
            decrementDownLimit();
            moveUp();
        }
    }
}


For Testing
final int[][] inputMatrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        final int[] expectedResult = {1, 2, 3, 6, 9, 8, 7, 4, 5};
        final MatrixTraverse matrixTraverse = new MatrixTraverseClock();

        Assert.assertArrayEquals(expectedResult,
                matrixTraverse.traverseMatrix(inputMatrix));


final int[] expectedResult1 = {1, 4, 7, 8, 9, 6, 3, 2, 5};
        final MatrixTraverse matrixTraverse = new MatrixTraverseCounterClock();

        Assert.assertArrayEquals(expectedResult1,
                matrixTraverse.traverseMatrix(inputMatrix));

Answer 1

A few remarks about your object-oriented design:

• It's odd that the matrixCount and up/down/left/rightLimits are part of the state of the object, but matrix itself isn't.
• I think matrix should be an instance variable along with all the others — in which case it should be passed into the constructor, not traverseMatrix().
• Alternatively, all of the variables would be local variables in traverseMatrix(int[][]). But that would be an excessively complex method. I don't recommend this.
• Class names should be nouns; method names should be verbs. I would rename MatrixTraverse and traverseMatrix() to MatrixTraverser and traverse(), respectively.
• You could consider this object an Iterator. I've written it that way in the solution below. Then you could have a convenience method called traverse() that repeatedly calls next() and assembles the whole array.

The main problem with your solution is lack of generality: up/down/left/right are each treated as special cases, so all of your code appears in quadruplicate.

You seem to have defined a TraverseDirection enum, which was not included in your post. I'll assume that it's just a dumb enum of four elements. You should make the enum more helpful.

We have an abstract base class, an enum, a clockwise iterator subclass, and an anticlockwise iterator subclass. For code organization, I would make the latter three static inner classes within the first. Inner classes would also save you from the repetitive naming (MatrixTraverse, TraversalDirection, MatrixTraverseClock, MatrixTraverseCounterClock).

An outline of the solution could be:

public abstract class MatrixTraverser implements Iterator<Integer> {
    protected static enum Direction {
        UP      (-1, 0),
        RIGHT   (0, +1),
        DOWN    (+1, 0),
        LEFT    (0, -1);

        public final int rowIncr, colIncr;

        /**
          * +1 if it represents "positive" movement; -1 if "negative" movement
          */
        public final int signum;

        private Direction(int rowIncr, int colIncr) {
            this.rowIncr = rowIncr;
            this.colIncr = colIncr;
            this.signum = this.rowIncr + this.colIncr;
        }
    }

    //////////////////////////////////////////////////////////////////////

    public static class Clockwise extends MatrixTraverser {
        public Clockwise(int[][] matrix) {
            super(matrix, Direction.RIGHT);
        }

        @Override
        protected Direction nextDirection(Direction direction) {
            switch (direction) {
              case RIGHT: return Direction.DOWN;
              case DOWN:  return Direction.LEFT;
              case LEFT:  return Direction.UP;
              case UP:    return Direction.RIGHT;
            }
            assert false;
            throw new IllegalArgumentException();
        }
    }

    //////////////////////////////////////////////////////////////////////

    public static class AntiClockwise extends MatrixTraverser {
        public AntiClockwise(int[][] matrix) {
            super(matrix, Direction.DOWN);
        }

        @Override
        protected Direction nextDirection(Direction direction) {
            switch (direction) {
              case DOWN:  return Direction.RIGHT;
              case RIGHT: return Direction.UP;
              case UP:    return Direction.LEFT;
              case LEFT:  return Direction.DOWN;
            }
            assert false;
            throw new IllegalArgumentException();
        }
    }

    public MatrixTraverser(int[][] matrix, Direction direction) {
        ...
    }

    public int[] traverse() {
        ...
    }

    ...
}

Each subclass of MatrixTraverser does the minimum necessary to specialize the general solution.

Oh, and here's the test case. Note that you can use it either as an iterator or call a convenience function to fetch the entire path at once.

public static void main(String[] args) {
    int[][] m = {{ 0,  1,  2,  3},
                 { 4,  5,  6,  7},
                 { 8,  9, 10, 11},
                 {12, 13, 14, 15}};

    MatrixTraverser t = new MatrixTraverser.Clockwise(m);
    while (t.hasNext()) {
        System.out.print(t.next() + " ");
    }
    System.out.println();

    int[] spiral = new MatrixTraverser.AntiClockwise(m).traverse();
    System.out.println(java.util.Arrays.toString(spiral));
}

At this point, you could try to fill in the blanks. Or, read on to see what I came up with.

---

private final int[][] matrix;
private int row, col;
private int itemsRemaining;
private Direction direction;
private int[] limits = new int[Direction.values().length];

public MatrixTraverser(int[][] matrix, Direction direction) {
    this.matrix = matrix;
    this.direction = direction;
    this.itemsRemaining = matrix.length * matrix[0].length;

    this.limits[Direction.DOWN.ordinal()] = matrix.length - 1;
    this.limits[Direction.RIGHT.ordinal()] = matrix[0].length - 1;

    // Stay out of row 0 or col 0 on the next round of the spiral
    this.limits[this.prevDirection(direction).ordinal()] = 1;
}

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

@Override
public boolean hasNext() {
    return this.itemsRemaining > 0;
}

@Override
public Integer next() {
    this.itemsRemaining--;
    int n = this.matrix[this.row][this.col];
    this.advance();
    return n;
}

private void advance() {
    int rowIncr = this.direction.rowIncr;
    int colIncr = this.direction.colIncr;
    this.row += rowIncr;
    this.col += colIncr;

    if ( (rowIncr < 0 && row == limits[Direction.UP.ordinal()]) ||
         (rowIncr > 0 && row == limits[Direction.DOWN.ordinal()]) ||
         (colIncr < 0 && col == limits[Direction.LEFT.ordinal()]) ||
         (colIncr > 0 && col == limits[Direction.RIGHT.ordinal()]) ) {
        this.limits[this.direction.ordinal()] -= this.direction.signum;
        this.direction = this.nextDirection(this.direction);
    }
}

protected abstract Direction nextDirection(Direction direction);

private Direction prevDirection(Direction direction) {
    for (Direction d : Direction.values()) {
        if (this.nextDirection(d) == direction) {
            return d;
        }
    }
    assert false;
    throw new IllegalArgumentException();
}

public int[] traverse() {
    int[] ret = new int[this.itemsRemaining];
    int i = 0;
    while (this.hasNext()) {
        ret[i++] = this.next();
    }
    return ret;
}