Leetcode 54
This is a page about »Leetcode 54«.
Leetcode 54 spiral matrix asked to return all elements in the given matrix in spiral order. The initial approach considered was to look at the traverse in two axes, the row and the column. Each iteration will go through one row and one column. The downside of this approach is that it requires the person coding to be very careful about the row- and column-iterating index. It involves index flipping and off by one error. Eventually, the working solution is provided by ChatGPT, obviously, the author quickly lost his patience during the index debugging. An easier way is to traverse a full loop (L->R, T->D, R->L, and D->T) in each iteration. This ensures that one can focus on the indexes one at a time instead of figuring out how to express them generically. The author was likely close to the correct solution and might have arrived at it with a few more minutes of focused problem-solving.
ChatGPT’s solution
1def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
2 if not matrix or not matrix[0]:
3 return []
4 top, bottom = 0, len(matrix) - 1
5 left, right = 0, len(matrix[0]) - 1
6 result = []
7 asc = True # Direction flag
8
9 while top <= bottom and left <= right:
10 if asc:
11 # Left to Right on top row
12 for col in range(left, right + 1):
13 result.append(matrix[top][col])
14 top += 1
15
16 # Top to Bottom on right column
17 for row in range(top, bottom + 1):
18 result.append(matrix[row][right])
19 right -= 1
20 else:
21 # Right to Left on bottom row
22 for col in range(right, left - 1, -1):
23 result.append(matrix[bottom][col])
24 bottom -= 1
25
26 # Bottom to Top on left column
27 for row in range(bottom, top - 1, -1):
28 result.append(matrix[row][left])
29 left += 1
30
31 asc = not asc # flip direction
32
33 return result
Alas, the author’s intended solution.
Simple Solution
1def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
2 result = []
3 if not matrix:
4 return result
5
6 top, bottom = 0, len(matrix) - 1
7 left, right = 0, len(matrix[0]) - 1
8
9 while top <= bottom and left <= right:
10 # Traverse from Left to Right
11 for col in range(left, right + 1):
12 result.append(matrix[top][col])
13 top += 1
14
15 # Traverse from Top to Bottom
16 for row in range(top, bottom + 1):
17 result.append(matrix[row][right])
18 right -= 1
19
20 # Traverse from Right to Left (only if there is a row remaining)
21 if top <= bottom:
22 for col in range(right, left - 1, -1):
23 result.append(matrix[bottom][col])
24 bottom -= 1
25
26 # Traverse from Bottom to Top (only if there is a column remaining)
27 if left <= right:
28 for row in range(bottom, top - 1, -1):
29 result.append(matrix[row][left])
30 left += 1
31
32 return result