Question:
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
Given the following matrix:
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
You should return
[1,2,3,6,9,8,7,4,5]
.Answers:
*************************************************************
Approach #1 Using Assitant Matrix
Intuition
This method is straight forward,
we are using an assistant matrix to help us
to record the visiting information,
i.e. when we meet the board or the element in the matrix has been visited,
we have to change the direction.
we are using an assistant matrix to help us
to record the visiting information,
i.e. when we meet the board or the element in the matrix has been visited,
we have to change the direction.
Algorithm
Here are some comments before going into the strategy:
1. we can visit all the elements in matrix[m,n] in m*n steps, so the loop is m*n and time complexity is $O(m*n)$
2. there are 4 directions, right ->down -> left -> up and the back to the right, the order of the direction will not change.
which means after going right and we have to change direction to down for sure.
3. how can we check if we have to change the direction or not?
a) when we reach the border of the matrix;
b) when we reach the elements we have been visited;
The strategy is as follows:
Step1: denote num_row as matrix.row_length, num_col as matrix.column_length
and initial checker[][] which help us to check if the elements in the matrix has been visited or not
Step2: while not finish visiting all the elements in matrix
-> check if can continue to go right
if yes
continue to go right and add the element in the result list
set the position in checker as true;
-> check if can continue to go down
if yes
continue to go down and add the element in the result list
set the position in checker as true;
-> check if can continue to go left
if yes
continue to go left and add the element in the result list
set the position in checker as true;
-> check if can continue to go up
if yes
continue to go up and add the element in the result list
set the position in checker as true;
Step3: return result list.
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if (matrix.length == 0)
return res;
int num_row = matrix.length;
int num_col = matrix[0].length;
boolean[][] checker = new boolean[num_row][num_col];
// Initial
int row = 0, col = 0, flag = 0;
res.add(matrix[row][col]);
checker[row][col] = true;
while (flag<num_row*num_col-1) {
// move right
while ((col + 1 < num_col) && (checker[row][col + 1] == false)) {
col++;
flag++;
res.add(matrix[row][col]);
checker[row][col] = true;
}
// move down
while ((row + 1 < num_row) && (checker[row + 1][col] == false)) {
row++;
flag++;
res.add(matrix[row][col]);
checker[row][col] = true;
}
// move left
while ((col > 0) && (checker[row][col - 1] == false)) {
col--;
flag++;
res.add(matrix[row][col]);
checker[row][col] = true;
}
// move up
while ((row > 0) && (checker[row - 1][col] == false)) {
row--;
flag++;
res.add(matrix[row][col]);
checker[row][col] = true;
}
}
return res;
}
}
Complexity Analysis
- Time complexity :
O(m∗n)
we just need to check all the elements in the matrix, and no repeat visiting. - Space complexity: $$O(mn)$$, we use checker matrix to store the visited elements information. and mn length result list.
Approach #2 Without Assisting Matrix [Accepted]
Can we do better? Can we design an algorithm not using helper matrix? Yes,
The strategy is: update matrix border.
As shown in the picture, every time we change the direction, we have to update border. For example,
first, we Go right as possible as we can and set blue as the new top border.
So we can not visit the first row anymore, the highest row we can visit becomes the second row (row+1)...
Therefore, we can implement the traverse strategy by updating the border.
The strategy is: update matrix border.
As shown in the picture, every time we change the direction, we have to update border. For example,
first, we Go right as possible as we can and set blue as the new top border.
So we can not visit the first row anymore, the highest row we can visit becomes the second row (row+1)...
Therefore, we can implement the traverse strategy by updating the border.
Algorithm
while(topBoarder<=bottomBoarder && leftBoarder <= rightBoarder)
1. go right as much as possible (when visiting the right border, go to 2)
increase top border;
2. go down as much as possible (when visiting the bottom border, go to 3)
decrease right border;
3. go left as much as possible (when visiting the left border, go to 4)
decrease bottom border;
4. go up as much as possible (when visiting the top border, back loop)
increase left boarder;
Java
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if (matrix.length == 0) {
return res;
}
int topBorder = 0, bottomBorder = matrix.length - 1;
int leftBorder = 0, rightBorder = matrix[0].length - 1;
while (topBorder <= bottomBorder && leftBorder <= rightBorder) {
// Traverse Right
for (int j = leftBorder; j <= rightBorder; j++) {
res.add(matrix[topBorder][j]);
}
topBorder++;
// Traverse Down
for (int j = topBorder; j <= bottomBorder; j++) {
res.add(matrix[j][rightBorder]);
}
rightBorder--;
if (topBorder <= bottomBorder) {
// Traverse Left
for (int j = rightBorder; j >= leftBorder; j--) {
res.add(matrix[bottomBorder][j]);
}
}
bottomBorder--;
if (leftBorder <= rightBorder) {
// Traverse Up
for (int j = bottomBorder; j >= topBorder; j--) {
res.add(matrix[j][leftBorder]);
}
}
leftBorder++;
}
return res;
}
}
A Comment
Please pay attention that before go in traverse left loop and traverse up loop,
there is an if statement. Why we need this?
Because that the top Boarder and right border have been updated.
if top Border > bottom Boarder which means the row == top Border == bottom Boarder has been visited, we do not need to visit once more.
In a word, this is to avoid duplications.
Please pay attention that before go in traverse left loop and traverse up loop,
there is an if statement. Why we need this?
Because that the top Boarder and right border have been updated.
if top Border > bottom Boarder which means the row == top Border == bottom Boarder has been visited, we do not need to visit once more.
In a word, this is to avoid duplications.
for example: the matrix just have one row {{1,2,3}};
after the traverse right loop, top border = 1;
after the traverse down loop, right border = 1;
not go into traverse left loop where top boarder = 1 > bottom boarder = 0;
not go into traverse up loop where top boarder = 1 > bottom boarder = 0;
Complexity Analysis
after the traverse right loop, top border = 1;
after the traverse down loop, right border = 1;
not go into traverse left loop where top boarder = 1 > bottom boarder = 0;
not go into traverse up loop where top boarder = 1 > bottom boarder = 0;
Complexity Analysis
- Time complexity: O(m*n)
- Space complexity: O(m*n). we use result list which length is m*n
Video Explanation
LeetCode Tutorial
Comments
Post a Comment