Spiral Matrix

• Initialize an empty list result to store the spiral order elements.
• If the input matrix is empty, return the empty list.
• Get the dimensions of the matrix, rows and cols.
• Create a visited boolean matrix of size rows x cols and initialize all its elements to false.
• Define the four directions of movement using two arrays: dr = {0, 1, 0, -1} for row changes and dc = {1, 0, -1, 0} for column changes, corresponding to right, down, left, and up.
• Initialize the starting position r = 0, c = 0, and the initial direction index di = 0.
• Iterate rows * cols times, as we need to visit every element once.
  • Add the element matrix[r][c] to the result list.
  • Mark the current cell as visited: visited[r][c] = true.
  • Calculate the coordinates of the next cell in the current direction: nextR = r + dr[di], nextC = c + dc[di].
  • Check if the next cell is out of bounds or has already been visited.
  • If the next cell is invalid, change the direction by updating the direction index: di = (di + 1) % 4.
  • Update the current position (r, c) for the next iteration using the (possibly new) direction.
• Return the result list.

The core idea is to walk the spiral path step by step. We start at the top-left corner (0, 0) and move right. We continue in one direction until we either hit the matrix boundary or a cell that we have already visited. When that happens, we turn right (e.g., from moving right to moving down) and continue. We repeat this process of moving and turning until we have visited all the cells in the matrix. A visited array is essential to keep track of our path and prevent infinite loops or incorrect traversals.

1class Solution {2    public List<Integer> spiralOrder(int[][] matrix) {3        List<Integer> result = new ArrayList<>();4        if (matrix == null || matrix.length == 0) {5            return result;6        }7        int rows = matrix.length;8        int cols = matrix[0].length;9        boolean[][] visited = new boolean[rows][cols];10        int[] dr = {0, 1, 0, -1}; // right, down, left, up11        int[] dc = {1, 0, -1, 0};12        int r = 0, c = 0, di = 0;13 14        for (int i = 0; i < rows * cols; i++) {15            result.add(matrix[r][c]);16            visited[r][c] = true;17            int nextR = r + dr[di];18            int nextC = c + dc[di];19 20            if (nextR >= 0 && nextR < rows && nextC >= 0 && nextC < cols && !visited[nextR][nextC]) {21                r = nextR;22                c = nextC;23            } else {24                di = (di + 1) % 4;25                r += dr[di];26                c += dc[di];27            }28        }29        return result;30    }31}

• Initialize an empty list result.
• If the input matrix is empty, return the empty list.
• Initialize four pointers to define the boundaries of the current layer: top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1.
• Start a loop that continues as long as top <= bottom and left <= right.
  • Traverse Right: Iterate from left to right along the top row, adding matrix[top][i] to result. After this traversal, increment top to shrink the boundary.
  • Traverse Down: Iterate from top to bottom along the right column, adding matrix[i][right] to result. After this, decrement right.
  • Check for single row/column cases: Before traversing left and up, check if top <= bottom and left <= right. This is crucial to handle matrices that are just a single row or a single column, preventing elements from being added twice.
  • Traverse Left: Iterate from right to left (in reverse) along the bottom row, adding matrix[bottom][i] to result. Then, decrement bottom.
  • Traverse Up: Iterate from bottom to top (in reverse) along the left column, adding matrix[i][left] to result. Then, increment left.
• The loop terminates when the boundaries cross, and all layers have been traversed. Return the result list.

This approach works by maintaining four pointers: top, bottom, left, and right, which represent the boundaries of the current layer of the matrix we are traversing. In each iteration of a main loop, we perform four traversals:

1. Move from left to right along the top boundary.
2. Move from top to bottom along the right boundary.
3. Move from right to left along the bottom boundary.
4. Move from bottom to top along the left boundary.

After each full cycle, we 'shrink' the boundaries inwards (top++, bottom--, left++, right--) to define the next, smaller concentric rectangle. The process continues until the boundaries cross each other (top > bottom or left > right). Special checks are needed after the first two traversals to correctly handle matrices with a single row or column.

1class Solution {2    public List<Integer> spiralOrder(int[][] matrix) {3        List<Integer> result = new ArrayList<>();4        if (matrix == null || matrix.length == 0) {5            return result;6        }7        int m = matrix.length;8        int n = matrix[0].length;9        int top = 0, bottom = m - 1;10        int left = 0, right = n - 1;11 12        while (top <= bottom && left <= right) {13            // Traverse Right14            for (int i = left; i <= right; i++) {15                result.add(matrix[top][i]);16            }17            top++;18 19            // Traverse Down20            for (int i = top; i <= bottom; i++) {21                result.add(matrix[i][right]);22            }23            right--;24 25            if (top <= bottom) { // Check if there's a row to traverse left26                // Traverse Left27                for (int i = right; i >= left; i--) {28                    result.add(matrix[bottom][i]);29                }30                bottom--;31            }32 33            if (left <= right) { // Check if there's a column to traverse up34                // Traverse Up35                for (int i = bottom; i >= top; i--) {36                    result.add(matrix[i][left]);37                }38                left++;39            }40        }41        return result;42    }43}