-
Notifications
You must be signed in to change notification settings - Fork 31
/
0054-spiral-matrix.rs
140 lines (123 loc) · 5.05 KB
/
0054-spiral-matrix.rs
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
/*
Problem: LeetCode 54 - Spiral Matrix
Key Idea:
The key idea is to simulate the process of traversing the matrix in a spiral order by defining four boundaries: top, bottom, left, and right.
Approach:
1. Initialize variables 'top' to 0, 'bottom' to the last row index, 'left' to 0, and 'right' to the last column index.
2. Initialize an empty vector 'result' to store the spiral order elements.
3. Use a loop to continue until 'top' is less than or equal to 'bottom' and 'left' is less than or equal to 'right'.
4. Inside the loop, iterate from 'left' to 'right' and add the elements in the top row to 'result'.
5. Increment 'top' to exclude the top row from further consideration.
6. Iterate from 'top' to 'bottom' and add the elements in the rightmost column to 'result'.
7. Decrement 'right' to exclude the rightmost column from further consideration.
8. Check if 'top' is still less than or equal to 'bottom' to avoid duplicate traversal.
9. Iterate from 'right' to 'left' and add the elements in the bottom row to 'result'.
10. Decrement 'bottom' to exclude the bottom row from further consideration.
11. Check if 'left' is still less than or equal to 'right' to avoid duplicate traversal.
12. Iterate from 'bottom' to 'top' and add the elements in the leftmost column to 'result'.
13. Increment 'left' to exclude the leftmost column from further consideration.
14. Repeat the loop until 'top' is no longer less than or equal to 'bottom' or 'left' is no longer less than or equal to 'right'.
15. Return the 'result' vector containing the elements in spiral order.
Time Complexity:
O(m * n), where 'm' is the number of rows and 'n' is the number of columns in the matrix. We visit each element once.
Space Complexity:
O(1), as we do not use any additional data structures that scale with the size of the input.
*/
impl Solution {
pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
if matrix.is_empty() {
return Vec::new();
}
let mut top = 0;
let mut bottom = matrix.len() as i32 - 1;
let mut left = 0;
let mut right = matrix[0].len() as i32 - 1;
let mut result = Vec::new();
while top <= bottom && left <= right {
for i in left..=right {
result.push(matrix[top as usize][i as usize]);
}
top = top.checked_add(1).unwrap();
for i in top..=bottom {
result.push(matrix[i as usize][right as usize]);
}
right = right.checked_sub(1).unwrap();
if top <= bottom {
for i in (left..=right).rev() {
result.push(matrix[bottom as usize][i as usize]);
}
bottom = bottom.checked_sub(1).unwrap();
}
if left <= right {
for i in (top..=bottom).rev() {
result.push(matrix[i as usize][left as usize]);
}
left = left.checked_add(1).unwrap();
}
}
result
}
}
/*
// Pattern Matching and Enums
enum Direction {
Up,
Down,
Right,
Left,
}
impl Solution {
pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
let mut current_direction = Direction::Right;
let mut current_round = 0;
let mut current_row = 0;
let mut current_col = 0;
let m = matrix.len();
let n = matrix[0].len();
let mut result = vec![];
for _ in 0..m * n {
result.push(matrix[current_row][current_col]);
match current_direction {
Direction::Up => {
// Check if we've reached the upper limit
if current_row == current_round + 1 {
current_col += 1;
current_direction = Direction::Right;
current_round += 1;
} else {
current_row -= 1;
}
}
Direction::Down => {
// Check if we've reached the lower limit
if current_row + 1 == m - current_round {
current_col -= 1;
current_direction = Direction::Left;
} else {
current_row += 1;
}
}
Direction::Right => {
// Check if we've reached the right limit
if current_col + 1 == n - current_round {
current_row += 1;
current_direction = Direction::Down;
} else {
current_col += 1;
}
}
Direction::Left => {
// Check if we've reached the left limit
if current_col == current_round {
current_row -= 1;
current_direction = Direction::Up;
} else {
current_col -= 1;
}
}
}
}
result
}
}
*/