Spiral Matrix
- 3 min read
- Array
- Matrix
- LC-Medium
3 years ago
Solution
- Same as Spiral Traverse but prefer the code in this, the algoexpert one uses a weird reversed thingy which I don't like
- Initialize
left,top,right, andbottomboundaries - While
left <= rightandtop <= bottom, do the following:- Traverse first row, increment
top - Traverse last column, decrement
right - Traverse last row in reverse, decrement
bottom - Traverse first column, increase
left
- Traverse first row, increment
- There are two edge cases: when there is one row and there is one column
- When there is one row:
- Only the first for loop would be printed
- The second for loop's boundary conditions are automatically invalid- so no need to extra checks
- Now, we need to check if
top <= bottom. Because if there was only one row, the first loop would've caused top to be incremented by one. And now it would mean it is greater than bottom. It has exceeded the bounds. We cannot print the bottom row because 1) we have already printed it, and 2) the top is> bottom
- Same thing for if there's only one column
- After the second for loop, right would be decremented. It would become lesser than left.
- This would mean we don't have to print the column, because 1) we have printed it already in the second for loop, and 2) our left and right boundaries are currently invalid.
| Time | Space | Explanation |
|---|---|---|
O(mn) | O(1) |
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
left, top = 0, 0
right, bottom = len(matrix[0]) - 1, len(matrix) - 1
ans = []
while left <= right and top <= bottom:
for c in range(left, right + 1):
ans.append(matrix[top][c])
top += 1
for r in range(top, bottom + 1):
ans.append(matrix[r][right])
right -= 1
if top <= bottom:
for c in range(right, left - 1, -1):
ans.append(matrix[bottom][c])
bottom -= 1
if left <= right:
for r in range(bottom, top - 1, -1):
ans.append(matrix[r][left])
left += 1
return ans
Alternate TS solution w/ 4-part pointer updates
function spiralOrder(matrix: number[][]): number[] {
let dir = 'R';
let sr = 0;
let sc = 0;
let nr = matrix.length - 1;
let nc = matrix[0].length - 1;
const ans = [];
while (sr <= nr && sc <= nc) {
for(let c = sc; c <= nc; c++) {
ans.push(matrix[sr][c]);
}
sr++;
if (sr > nr) {
break;
}
for(let r = sr; r <= nr; r++) {
ans.push(matrix[r][nc]);
}
nc--;
if (nc < sc) {
break;
}
for(let c = nc; c >= sc; c--) {
ans.push(matrix[nr][c]);
}
nr--;
if(nr < sr) {
break;
}
for(let r = nr; r >= sr; r--) {
ans.push(matrix[r][sc]);
}
sc++;
if (sc > nc) {
break;
}
}
return ans;
};