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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
}