Fork me on GitHub

Spiral Matrix I && II

Posted on

Linkage

https://leetcode.com/problems/spiral-matrix/description/

Easy to implement the alogithm, but pay attention to the bounds.

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
class Solution {
    public enum Direction {  
        LEFT, RIGHT, UP, DOWN 
    }
    public List<Integer> spiralOrder(int[][] matrix) {
        int row_length = matrix.length;
        List<Integer> ret = new LinkedList<Integer>();
        if (row_length == 0)
            return ret;
        int column_length = matrix[0].length;
        
        Direction direction = Direction.RIGHT;
        int row = 0;
        int column = 0;
        int remain = row_length * column_length;
        int left_bound = 0;
        int right_bound = column_length - 1;
        int up_bound = 0;
        int down_bound = row_length - 1;
        
        while(remain > 0){
            switch (direction){
                case RIGHT:
                    for(; column <= right_bound && remain > 0; ++column){
                        remain -= 1;
                        ret.add(matrix[row][column]);
                    }
                    column -= 1;
                    row += 1;
                    up_bound += 1;
                    
                    direction = Direction.DOWN;
                    break;
                case DOWN:
                    for(; row <= down_bound && remain > 0; ++row){
                        remain -= 1;
                        ret.add(matrix[row][column]);
                    }
                    row -= 1;
                    column -= 1;
                    right_bound -= 1;
                    direction = Direction.LEFT;
                    break;
                case LEFT:
                    for(; column >= left_bound && remain > 0; --column){
                        remain -= 1;
                        ret.add(matrix[row][column]);
                    }
                    column += 1;
                    row -= 1;
                    down_bound -= 1;
                    direction = Direction.UP;
                    break;
                case UP:
                    for(; row >= up_bound && remain > 0; --row){
                        remain -= 1;
                        ret.add(matrix[row][column]);
                    }
                    row += 1;
                    column += 1;
                    left_bound += 1;
                    direction = Direction.RIGHT;
                    break;
            }
        }
        return ret;
    }
}

Follow up

https://leetcode.com/problems/spiral-matrix-ii/description/

Code

In this problem, we found the fact that the direction change is regular, namely, it follows right, down, left, up, right, down, left, up. So we can simplify the code from switch case to simple loop.This polishment also add the speed of calculation compared to the switch way.

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
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ret = new int[n][n];
        int row = 0, col = 0;
        
        int count = 1;
        int sum = n*n;
        int left_bound = 0, right_bound = n - 1, up_bound = 0, down_bound = n - 1;
        
        while (count <= sum) {
            while(col <= right_bound && count <= sum) {
                ret[row][col] = count++;
                col += 1;
            }
            col -= 1;
            up_bound += 1;
            row += 1;
            while(row <= down_bound && count <= sum) {
                ret[row][col] = count++;
                row += 1;
            }
            row -= 1;
            right_bound -= 1;
            col -= 1;
            while(col >= left_bound && count <= sum) {
                ret[row][col] = count++;
                col -= 1;
            }
            col += 1;
            down_bound -= 1;
            row -= 1;
            while(row >= up_bound && count <= sum) {
                ret[row][col] = count++;
                row -= 1;
            }
            row += 1;
            col += 1;
            left_bound += 1;
        }
    
        return ret;
    }
}