Bernice Waweru
Posted on October 31, 2022
Instructions
Given an m x n matrix, return all elements of the matrix in spiral order.
Input: matrix = [
[1,2,3],
[4,5,6],
[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Attempt the question.
Approach
- The output follows a clockwise motion; we move to the left, then downwards, upwards and finally to the right.
We initialize four pointer; left,right,top and bottom.
Then move from left to right and update the top pointer to the next row because we are done with the given row.
Then move from current top to bottom to cover elements on the rightmost column and update the right pointer.
Move from right to left in the bottom most row and update the bottom pointer.
Move from bottom to top and update the left pointer.
This process continues until the left and right pointer meet or the top and bottom pointer meet.
Implementation
def spiralOrder(matrix):
left, right = 0, len(matrix[0])
top, bottom = 0, len(matrix)
spiral = []
while (top < bottom and left < right):
# left to right
for i in range(left, right):
spiral.append(matrix[top][i])
top += 1
# right to bottom
for i in range(top, bottom): # does not repeat value because we have updated top
spiral.append(matrix[i][right-1])
right -= 1
if not (top < bottom and left < right):
break
# right to left
for i in range(right-1, left-1, -1):
spiral.append(matrix[bottom-1][i])
bottom -= 1
# top to bottom
for i in range(bottom-1, top-1, -1):
spiral.append(matrix[i][left])
left +=1
return spiral
Happy learning !!
References
💖 💪 🙅 🚩
Bernice Waweru
Posted on October 31, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
