54. Spiral Matrix Medium

1/**
2 * [54] Spiral Matrix
3 *
4 * Given an m x n matrix, return all elements of the matrix in spiral order.
5 *  
6 * Example 1:
7 * <img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/spiral1.jpg" style="width: 242px; height: 242px;" />
8 * Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
9 * Output: [1,2,3,6,9,8,7,4,5]
10 *
11 * Example 2:
12 * <img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/spiral.jpg" style="width: 322px; height: 242px;" />
13 * Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
14 * Output: [1,2,3,4,8,12,11,10,9,5,6,7]
15 *
16 *  
17 * Constraints:
18 *
19 * m == matrix.length
20 * n == matrix[i].length
21 * 1 <= m, n <= 10
22 * -100 <= matrix[i][j] <= 100
23 *
24 */
25pub struct Solution {}
26
27// problem: https://leetcode.com/problems/spiral-matrix/
28// discuss: https://leetcode.com/problems/spiral-matrix/discuss/?currentPage=1&orderBy=most_votes&query=
29
30// submission codes start here
31
32impl Solution {
33    pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
34        let mut result = vec![];
35        if matrix.is_empty() {
36            return result;
37        }
38
39        let mut top = 0;
40        let mut bottom = matrix.len() - 1;
41        let mut left = 0;
42        let mut right = matrix[0].len() - 1;
43
44        loop {
45            for i in left..right + 1 {
46                result.push(matrix[top][i]);
47            }
48            top += 1;
49            if top > bottom || right < left {
50                break;
51            }
52
53            for j in top..bottom + 1 {
54                result.push(matrix[j][right]);
55            }
56            if right == 0 {
57                break;
58            }
59            right -= 1;
60            if top > bottom || right < left {
61                break;
62            }
63
64            for i in (left..right + 1).rev() {
65                result.push(matrix[bottom][i]);
66            }
67            if bottom == 0 {
68                break;
69            }
70            bottom -= 1;
71            if top > bottom || right < left {
72                break;
73            }
74
75            for j in (top..bottom + 1).rev() {
76                result.push(matrix[j][left]);
77            }
78            left += 1;
79            if top > bottom || right < left {
80                break;
81            }
82        }
83        result
84    }
85}
86
87// submission codes end
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92
93    #[test]
94    fn test_54() {
95        assert_eq!(
96            Solution::spiral_order(vec![
97                vec![1, 2, 3, 4],
98                vec![5, 6, 7, 8],
99                vec![9, 10, 11, 12]
100            ]),
101            vec![1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
102        );
103    }
104
105    #[test]
106    fn test_54_1() {
107        assert_eq!(
108            Solution::spiral_order(vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]]),
109            vec![1, 2, 3, 6, 9, 8, 7, 4, 5]
110        );
111    }
112
113    #[test]
114    fn test_54_2() {
115        assert_eq!(Solution::spiral_order(vec![vec![1, 2, 3]]), vec![1, 2, 3]);
116    }
117
118    #[test]
119    fn test_54_3() {
120        assert_eq!(
121            Solution::spiral_order(vec![vec![1], vec![2], vec![3]]),
122            vec![1, 2, 3]
123        );
124    }
125}
126