Question

link

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

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

You should return [1,2,3,6,9,8,7,4,5].

Stats

Frequency	2
Difficulty	4
Adjusted Difficulty	3
Time to use	----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is basic mathematics. The difficulty is the coding part.

My code

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0
            || matrix[0] == null || matrix[0].length == 0) {
            return ans;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int a = 0;
        int b = 0;
        while (a < (m + 1) / 2 && b < (n + 1) / 2) {
            // special cases
            if (2 * a + 1 == m && 2 * b + 1 == n) {
                ans.add(matrix[a][b]);
                break;
            } else if (2 * a + 1 == m) {
                for (int j = b; j <= n - 1 - b; j++) {
                    ans.add(matrix[a][j]);
                }
                break;
            } else if (2 * b + 1 == n) {
                for (int i = a; i <= m - 1 - a; i++) {
                    ans.add(matrix[i][b]);
                }
                break;
            }
            // now is the general case
            // first horizontal row without last element
            for (int j = b; j < n - 1 - b; j++) {
                ans.add(matrix[a][j]);
            }
            // vertical column on right-hand side
            for (int i = a; i < m - 1 - a; i++) {
                ans.add(matrix[i][n - 1 - b]);
            }
            for (int j = n - 1 - b; j > b; j--) {
                ans.add(matrix[m - 1 - a][j]);
            }
            for (int i = m - 1 - a; i > a; i--) {
                ans.add(matrix[i][b]);
            }
            a++;
            b++;
        }
        return ans;
    }
}

Updated Oct 29, 2022

    public List<Integer> spiralOrder(int[][] matrix) {
        int[][] direct = {
            {0, 1},
            {1, 0},
            {0, -1},
            {-1, 0}
        };
        int m = matrix.length;
        int n = matrix[0].length;
        List<Integer> ans = new LinkedList<Integer>();
        boolean[][] visited = new boolean[m][n];

        int x = 0;
        int y = 0;
        int k = 0;
        while (ans.size() < m * n) {
            visited[x][y] = true;
            ans.add(matrix[x][y]);
            int nextX = x + direct[k][0];
            int nextY = y + direct[k][1];
            if (nextX < 0 || nextX >= m
                    || nextY < 0 || nextY >= n
                    || visited[nextX][nextY]) {
                k = (k + 1) % 4;
                x += direct[k][0];
                y += direct[k][1];
            } else {
                x = nextX;
                y = nextY;
            }
        }
        return ans;
    }