Given an m x n matrix, return all elements of the matrix in spiral order.

Overview

Optimal Solution

We need to traverse the array from the start column and go through the whole perimeter of the array. Then we can repeat the iteration on the inner perimeter of the array until we traversed the whole array.

Flow Diagram

Traverse each border and repeat. Make sure to not double count elements. Needs attention on the edges and on the loops to include the edges.

This solution is based on keeping track of the startCol, endCol, startRow and endRow variables. No need to keep track of direction.

Time Complexity

As we are traversing the whole array once, the time complexity is O(n). No other complex operation needed.

Space Complexity

Space complexity will be O(n) as we are creating a new array with N elements to store the iterated values.

Java Source Code

    public List<Integer> spiralTraverse(final int[][] array) {
        final List<Integer>  result = new ArrayList<>();

        var startRow = 0;
        var endRow = array.length-1;
        var startCol = 0;
        var endCol = array[0].length-1;

        while(startRow <= endRow && startCol <= endCol) {
            for(var i=startCol;i<=endCol;i++) { /* top border */
                result.add(array[startRow][i]);
            }

            for(var i=startRow+1;i<=endRow;i++) { /* right border */
                result.add(array[i][endCol]);
            }

            for(var i=endCol-1;i>=startCol;i--) { /* bottom border */
                if (startRow == endRow) break;
                result.add(array[endRow][i]);
            }

            for(var i=endRow-1;i>startRow;i--) { /* left border */

                if (startCol == endCol) break;
                result.add(array[i][startCol]);
            }

            startRow++;
            endRow--;
            startCol++;
            endCol--;
        }

        return result;
    }

Conclusion

Rockets often spiral out of control if you put too much propellant in them.

Steve Jurveston