Topics › Arrays › Medium

Print the matrix in spiral manner

Medium TUF ID 33 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given an n × m matrix, return all of its elements in spiral order: start at the top-left corner, move right along the top row, then down the right column, then left along the bottom row, then up the left column, and keep spiralling inward until every element has been visited.

Constraints: 1 ≤ n, m ≤ 10 on LeetCode (the code also handles an empty matrix); the matrix need not be square. Values fit in a 32-bit signed integer.

Example 1

matrix = [[1, 2, 3],
          [4, 5, 6],
          [7, 8, 9]]
answer = [1, 2, 3, 6, 9, 8, 7, 4, 5]

Example 2

matrix = [[1,  2,  3,  4],
          [5,  6,  7,  8],
          [9, 10, 11, 12]]
answer = [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]   // after the outer ring only 6, 7 remain

There is no asymptotically “slow” solution here: any correct method must output all n·m elements, so every approach is O(n·m) time. The two approaches differ in how they keep track of where to go next and in how much extra memory that takes.

Approach 1: Simulation with a visited matrix

Intuition. Imagine a robot on the top-left cell facing right. It emits the cell it stands on and tries to step forward. If the cell ahead is off the grid or has already been emitted, it turns 90 degrees clockwise and steps. That is literally the definition of a spiral. The robot needs to remember which cells it has visited, hence a boolean matrix the size of the input. The direction cycle is right, down, left, up, encoded as index dir into two small arrays of row and column deltas.

Algorithm.

1. If the matrix is empty return an empty list. Allocate visited[n][m].
2. Start at (0, 0) with dir = 0 (right).
3. Repeat n·m times: emit matrix[r][c], mark it visited, compute the next cell (nr, nc). If it is out of bounds or visited, turn (dir = (dir + 1) % 4) and recompute. Move to (nr, nc).

static List<Integer> simulation(int[][] matrix) {
    List<Integer> ans = new ArrayList<>();
    int n = matrix.length, m = n == 0 ? 0 : matrix[0].length;
    if (n == 0 || m == 0) return ans;
    boolean[][] visited = new boolean[n][m];
    int[] dr = {0, 1, 0, -1};                     // right, down, left, up
    int[] dc = {1, 0, -1, 0};
    int r = 0, c = 0, dir = 0;
    for (int step = 0; step < n * m; step++) {
        ans.add(matrix[r][c]);
        visited[r][c] = true;
        int nr = r + dr[dir], nc = c + dc[dir];
        if (nr < 0 || nr >= n || nc < 0 || nc >= m || visited[nr][nc]) {
            dir = (dir + 1) % 4;                  // turn clockwise
            nr = r + dr[dir];
            nc = c + dc[dir];
        }
        r = nr;
        c = nc;
    }
    return ans;
}

Complexity. Time O(n·m): exactly n·m iterations with constant work each. Space O(n·m) for the visited matrix, on top of the output.

Why is a single turn always enough? After a turn the robot is facing the next side of the current ring, and that side always has at least one unvisited cell unless all n·m cells are done, in which case the loop ends anyway. On the very last iteration (nr, nc) may be invalid, but it is never read.

Approach 2: Optimal, four shrinking boundaries

Intuition. Instead of remembering individual cells, remember the rectangle that is still unvisited: top, bottom, left, right. One round of the spiral prints the four sides of that rectangle and then shrinks it by one on every side. Printing the top row means “row top, columns left..right”, and once it is printed, top++. Likewise for the other three sides. This needs four integers instead of an n × m boolean matrix.

The one subtlety is the last round. When only a single row remains (top == bottom), printing the top row and then the bottom row would print the same cells twice. The same happens for a single remaining column. So after the first two sides, check that the rectangle is still non-empty before printing the bottom row and the left column.

Algorithm.

1. top = 0, bottom = n - 1, left = 0, right = m - 1.
2. While top <= bottom && left <= right:
   • print row top from left to right; top++;
   • print column right from top to bottom; right--;
   • if top <= bottom: print row bottom from right down to left; bottom--;
   • if left <= right: print column left from bottom up to top; left++.

static List<Integer> optimal(int[][] matrix) {
    List<Integer> ans = new ArrayList<>();
    int n = matrix.length, m = n == 0 ? 0 : matrix[0].length;
    int top = 0, bottom = n - 1, left = 0, right = m - 1;
    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; j++) ans.add(matrix[top][j]);        // top row, left to right
        top++;
        for (int i = top; i <= bottom; i++) ans.add(matrix[i][right]);      // right column, top to bottom
        right--;
        if (top <= bottom) {                                                 // bottom row, right to left
            for (int j = right; j >= left; j--) ans.add(matrix[bottom][j]);
            bottom--;
        }
        if (left <= right) {                                                 // left column, bottom to top
            for (int i = bottom; i >= top; i--) ans.add(matrix[i][left]);
            left++;
        }
    }
    return ans;
}

Dry run on example 2 (3 × 4):

The outer while then stops because top > bottom. Output: 1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7.

Complexity. Time O(n·m): every cell is added exactly once. Space O(1) beyond the output list.

Why do the two guards suffice? After printing the top row and the right column, the only way to double-print is if the remaining rectangle has collapsed to zero rows (top > bottom) or zero columns (left > right). The bottom-row guard handles the first case; the left-column guard handles the second. In the dry run above, the left-column step in round 2 passes the guard but its loop is empty because bottom < top, which is harmless.

Edge cases and pitfalls

• Single row. [[1, 2, 3, 4, 5]]: the top row prints everything, and the bottom-row guard top <= bottom fails, preventing a reversed reprint.
• Single column. [[1], [2], [3], [4]]: the top row prints 1, the right column prints 2, 3, 4, and the left-column guard left <= right fails after right--.
• Tall or wide inner rectangles. [[1, 2], [3, 4], [5, 6]] leaves a single column 3, 5 after the first partial round; the test 3 × 2 -> [1, 2, 4, 6, 5, 3] checks that the inner pass does not repeat anything.
• 1 × 1. Prints the single element once.
• Empty matrix. Both methods return an empty list: the simulation checks explicitly, and the boundary loop never starts because bottom = -1.
• Off-by-one in the boundary loops. The right column must start at the updated top and the bottom row at the updated right, otherwise corners are printed twice. The code increments top and decrements right before those loops.
• Forgetting to turn only once. In the simulation, after a turn the new cell is always valid (see above), so a single if, not a while, is correct and simpler.

Related problems

• Rotate matrix by 90 degrees also processes a matrix ring by ring.
• Set Matrix Zeroes is another matrix traversal where the order of operations matters.
• Next Permutation is another problem whose whole solution is a carefully chosen traversal.