/ Data Structure and Algorithms  

Leetcode 54. Spiral Matrix

Question



Give a m * n matrix, return the spiral order of all elements.

Similar Questions

Solution

Start at the first position and walk along the boundary. When reach the boundary, change direction and continue until complete all positions.



There is no magic here, just simulate the process.

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> results = new ArrayList<>();

    if (matrix.length == 0) {
        return results;
    }

    // current index of the position
    int indexX = 0;
    int indexY = 0;

    // up, right, down, left
    int[][] direction = new int[][]{
            {0, -1},
            {1, 0},
            {0, 1},
            {-1, 0}
    };

    // moving direction, start towards right
    Towards towards = Towards.RIGHT;

    // mark the position of boundary
    int topBorder = -1;
    int bottomBorder = matrix.length;
    int leftBorder = -1;
    int rightBorder = matrix[0].length;

    while (true) {
        // finished
        if (results.size() == matrix.length * matrix[0].length) {
            return results;
        }

        results.add(matrix[indexY][indexX]);

        switch (towards) {
            // move right
            case RIGHT:
                // reach the boundary
                if (indexX + 1 == rightBorder) {
                    // change direction
                    towards = Towards.DOWN;
                    // move the boundary
                    topBorder++;

                    // moving toward down
                    indexY += direction[towards.ordinal()][1];
                } else {
                    indexX += direction[towards.ordinal()][0];
                }

                break;
            // move down
            case DOWN:
                if (indexY + 1 == bottomBorder) {
                    towards = Towards.LEFT;
                    rightBorder--;

                    indexX += direction[towards.ordinal()][0];
                } else {
                    indexY += direction[towards.ordinal()][1];
                }

                break;
            // move left
            case LEFT:
                if (indexX - 1 == leftBorder) {
                    towards = Towards.UP;
                    bottomBorder--;

                    indexY += direction[towards.ordinal()][1];
                } else {
                    indexX += direction[towards.ordinal()][0];
                }
                break;
            // move up
            case UP:
                if (indexY - 1 == topBorder) {
                    towards = Towards.RIGHT;
                    leftBorder++;

                    indexX += direction[towards.ordinal()][0];
                } else {
                    indexY += direction[towards.ordinal()][1];
                }
                break;
        }
    }
}

private enum Towards {
    UP, RIGHT, DOWN, LEFT
}