The Blind 75 Leetcode Series: Spiral Matrix

Today, we will be working on 54. Spiral Matrix.

Given an m x n matrix, return all elements of the matrix in spiral order.

Without the constraints, we can check several things

  1. Is the matrix always going to be present?
  2. What’s inside the matrix? Does it matter?
  3. Is it ever possible to have an invalid matrix? What do we do when that happens?

If the answers are 1) yes, 2) what’s inside is simply integrers, and 3) the matrix is always going to be valid.

Then we know we will always have a rectangular shape list of list filled with integers. We then just need to follow the matrix and print out all numbers.

The most important aspect of this question is to know when to “turn”. If we start going right of the matrix, we turn to the right (which is facing “down”) when we hit the end of the matrix. We then turn again when we get to the bottom of the matrix. Once we hit the element at matrix[1][0], we have to somehow know that we have already visited the matrix[0][0] so we cannot go there again. At the end, we need to know when to stop when we have visited all the elements.

So, we have several things to track

  1. current position
  2. size of the matrix so we know when we hit the wall
  3. the direction we are taking
  4. elements we have visited
  5. if we have visited all the elements

We can achieve 1 and 2 but simply assigning the size and positions to variables. Let’s make m=len(matrix) and n = len(matrix[0]) , effectively getting length and width of the matrix. Let’s then use i and j to indicate the current position. Since we are always starting from the top left corner, we can assign both to 0.

For 3, we start with going right, when we hit the wall of hit an element we have already visited, we turn. Directions go right -> down -> left -> up -> right -> … , and we know to switch to the next one when triggered.

For 4, we can have a tracking map with the size of the matrix filled with 0s. Using i and j, we can easily flip the 0 to 1 to know we have visited such element.

For 5, We can either use the same tracker, checking of the sum of all elements == size of matrix (m x n), if so, we know we have visited all elements. Another way is to simply use another integer. Every time we visit an element, we increment it.

The code will look like this

# append next element to output, mark tracker, and increment visited
def fill(output, matrix, i, j, tracker, visited):
output.append(matrix[i][j])
tracker[i][j] = 1
visited += 1
return visited
def spiralOrder(matrix):
# early return if size of matrix is 1
if len(matrix) == 1:
return matrix[0]
output = []
m = len(matrix)
n = len(matrix[0])
# initial tracker is all 0s, top-left corner, direction='right'. Mark the first element and corresponding actions
tracker = [[0] * n for _ in range(m)]
i = j = 0
current_dir = 'r'
output.append(matrix[i][j])
tracker[i][j] = 1
visited = 1
# stop when hitting all elements
while visited < m * n:
if current_dir == 'r':
# when hitting right wall or visited ele, turn "down"
while j < n - 1 and tracker[i][j+1] == 0:
j += 1
visited = fill(output, matrix, i, j, tracker, visited)
current_dir = 'd'
elif current_dir == 'd':
# when hitting bottom wall or visited ele, turn "left"
while i < m - 1 and tracker[i+1][j] == 0:
i += 1
visited = fill(output, matrix, i, j, tracker, visited)
current_dir = 'l'
elif current_dir == 'l':
# when hitting left wall or ele, turn "up"
while j > 0 and tracker[i][j-1] == 0:
j -= 1
visited = fill(output, matrix, i, j, tracker, visited)
current_dir = 'u'
elif current_dir == 'u':
# when hitting upper wall or ele, turn "right"
while i > 0 and tracker[i-1][j] == 0:
i -= 1
visited = fill(output, matrix, i, j, tracker, visited)
current_dir = 'r'
return output

The time complexity for this is quite simple. We visit all elements once and track it, so we have O(m*n) where m and n are length and width of the matrix.

What’s another way to solve this problem? If you noticed, the way we “turn” our direction can be seen as turning the matrix in the opposite direction. In this problem, we can turning the direction clockwise, so we can instead turning the matrix in counter-clockwise direction and grab the top row.

[
1 2 3 [1 2 3] # pop the first row
4 5 6 => [6 9 # turn the rest counter cw
7 8 9 5 8
] 4 7]

[1 2 3 6 9] # pop first row again
[8 7 # turn the rest counter clockwise
5 4
]
[1 2 3 6 9 8 7]
[4
5
]
[1 2 3 6 9 8 7 4]
[5]
[1 2 3 6 9 8 7 4 5] # this is our answer

We loop through the same actions until there’s no more element in the matrix:

  1. pop first row of matrix
  2. rotate the matrix counter clockwise

Rotating a matrix….. sounds familiar. If you have been following this series, you might have seen this problem.

We can apply the same logic here. We want to rotate counter clockwise, so we reverse then trasnpose. We do need some modifications since the matrix is no longer always a square. We will have to rebuild the transpose function to create a new matrix. Everything else stays the same though

def transpose(matrix):
m = len(matrix)
n = len(matrix[0])
new_matrix = [[0]*m for _ in range(n)]
for i in range(m):
for j in range(n):
new_matrix[j][i] = matrix[i][j]
return new_matrix
def reverse(matrix):
print(matrix)
m = len(matrix)
n = len(matrix[0])
for i in range(m):
for j in range(n//2):
matrix[i][j], matrix[i][-j-1] = matrix[i][-j-1], matrix[i][j]
def rotate(matrix):
reverse(matrix)
new_matrix = transpose(matrix)
return new_matrix
def recursive(matrix, output):
output.extend(list(matrix.pop(0)))
if len(matrix) == 0:
return output
new_matrix = rotate(matrix)
return recursive(new_matrix, output)
def spiralOrder(matrix):
output = []
return recursive(matrix, output)

Now, this approach takes longer time as we need to reverse and transpose the matrix every time, and we still need to take every element.

I would recommend using the first solution as it’s faster and more intuitive. I wouldn’t worry too much about not knowing the matrix property unless, say, you’re interviewing for some imaging/data science/ML positions.

Here you go! Another problem down.

Buy my a coffee: https://www.buymeacoffee.com/jonathanckz

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store