• Explanation: The elements are traversed in a spiral order, starting from the top-left corner and moving right, down, left, and up, until all elements are visited.
• Explanation: The elements are collected in a spiral order: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7].
Approach: The approach uses a systematic way to traverse the matrix in a spiral order by adjusting boundaries after processing each row and column.
Observations:
• We need to handle four directions: left to right, top to bottom, right to left, and bottom to top.
• As we traverse the matrix, the boundaries (top, bottom, left, right) will be reduced progressively.
• This problem can be solved in linear time by maintaining and updating boundaries during the traversal.
Steps:
• 1. Initialize variables to track the current boundaries (top, bottom, left, right).
• 2. Loop until the entire matrix is processed: traverse the matrix in four steps: left to right, top to bottom, right to left, and bottom to top.
• 3. After each traversal, adjust the boundary by incrementing or decrementing the respective row or column.
• 4. Return the list of elements after the entire matrix is traversed.
Empty Inputs:
• The problem guarantees that the matrix will have at least one row and one column.
Large Inputs:
• The solution must handle the maximum matrix size (10x10) efficiently.
Special Values:
• If the matrix contains negative values or zeros, the traversal should still proceed in the same spiral order.
Constraints:
• The solution must be efficient in terms of time and space complexity.
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int rows = matrix.size(), cols = matrix[0].size();
int top =0, bottom = rows -1, left =0, right = cols -1;
vector<int> result;
while (top <= bottom && left <= right) {
// Traverse Right
for (int i = left; i <= right; i++) {
result.push_back(matrix[top][i]);
}
top++;
// Traverse Down
for (int i = top; i <= bottom; i++) {
result.push_back(matrix[i][right]);
}
right--;
// Traverse Left
if (top <= bottom) {
for (int i = right; i >= left; i--) {
result.push_back(matrix[bottom][i]);
}
bottom--;
}
// Traverse Up
if (left <= right) {
for (int i = bottom; i >= top; i--) {
result.push_back(matrix[i][left]);
}
left++;
}
}
return result;
}
This line declares a function named `spiralOrder` that takes a 2D vector `matrix` as input and returns a vector containing the elements in spiral order.
2 : Variable Initialization
int rows = matrix.size(), cols = matrix[0].size();
This line initializes variables `rows` and `cols` to store the number of rows and columns in the matrix, respectively.
3 : Boundary Initialization
int top =0, bottom = rows -1, left =0, right = cols -1;
This line initializes variables to track the boundaries of the current spiral traversal: `top`, `bottom`, `left`, and `right`.
4 : Result Vector Initialization
vector<int> result;
This line initializes an empty vector `result` to store the spiral order elements.
5 : Spiral Traversal Loop
while (top <= bottom && left <= right) {
This loop continues as long as there are elements to be traversed in the spiral.
6 : Traverse Right
for (int i = left; i <= right; i++) {
result.push_back(matrix[top][i]);
}
This loop traverses the top row from left to right, adding elements to the `result` vector.
7 : Update Top Boundary
top++;
After traversing the top row, the `top` boundary is incremented to exclude the processed row.
8 : Traverse Down
for (int i = top; i <= bottom; i++) {
result.push_back(matrix[i][right]);
}
This loop traverses the rightmost column from top to bottom, adding elements to the `result` vector.
9 : Update Right Boundary
right--;
After traversing the right column, the `right` boundary is decremented to exclude the processed column.
10 : Traverse Left (Conditional)
if (top <= bottom) {
This conditional check ensures that there's still a row to traverse from right to left.
11 : Traverse Left
for (int i = right; i >= left; i--) {
result.push_back(matrix[bottom][i]);
}
This loop traverses the bottom row from right to left, adding elements to the `result` vector.
12 : Update Bottom Boundary
bottom--;
After traversing the bottom row, the `bottom` boundary is decremented to exclude the processed row.
13 : Traverse Up (Conditional)
if (left <= right) {
This conditional check ensures that there's still a column to traverse from bottom to top.
14 : Traverse Up
for (int i = bottom; i >= top; i--) {
result.push_back(matrix[i][left]);
}
This loop traverses the leftmost column from bottom to top, adding elements to the `result` vector.
15 : Update Left Boundary
left++;
After traversing the left column, the `left` boundary is incremented to exclude the processed column.
16 : Return Result
return result;
The function returns the `result` vector containing the elements in spiral order.
Best Case: O(m * n)
Average Case: O(m * n)
Worst Case: O(m * n)
Description: The algorithm processes every element of the matrix exactly once, so the time complexity is O(m * n).
Best Case: O(1)
Worst Case: O(m * n)
Description: The space complexity is O(m * n) for storing the result, but the in-place traversal itself requires O(1) space.
