Python Program to Print a Spiral Matrix

The problem statement for this tutorial is: given a 2D matrix, we must design an algorithm to print it in spiral form as a 1D array. We will implement this algorithm in Python.

Example input and output for understanding the problem:

Input: {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}}
Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Input: { {1, 3, 5, 7, 9, 11},
{0, 2, 4, 6, 8, 10},
{12, 13, 14, 15, 16}}
Output: 1, 3, 5, 7, 9, 11, 10, 16, 15, 14, 13, 12, 0, 2, 4, 6, 8

<h2>Solving the Problem Using Simulation</h2>
<p>We will follow this idea and solve the problem using simulation:

<p>We will draw a spiral path for a given matrix or 2D array. The spiral path must move in a clockwise direction. It will only change its path or turn at the edges so that the loop does not exceed the boundaries of the matrix.

<p><strong>Here are the steps to follow:

<p> * Assume that the matrix has m rows and n columns. <br>
* Visited[m] represents the cell at row m and column n that we have visited. Our current position in the matrix is denoted as (m, n). It has a direction d, and we must traverse m×n cells. <br>
* As the traversal continues, the pointer's next position will be represented by (nr, nc). <br>
* If the pointer is on a cell at the matrix boundary and has not yet seen it, it will be rotated 90 degrees clockwise, and then it will become the pointer's next position, which is (nr, nc). </p>
<p>Now we will implement this method in Python. </p>
<p><strong>Code</strong></p>
<pre><code class="language-python line-numbers"># Python program that prints the spiral form of a matrix using the analog method

# Define a function that will take a matrix and return its spiral form
def spiralform(matrix):

spiral = []

# Return an empty array if there are no elements in the matrix

if (len(matrix) == 0):

Return the spiral form

# Store the number of rows, m, and columns, n, of the matrix

m = len(matrix)

n = len(matrix[0])

# Create an empty matrix the same size as the original matrix

visit = [[0 for i in range(n)] for j in range(m)]

# Initialize the direction vector and coordinates

dr = [0,1,0,-1]

dc = [1,0,-1,0]

x = 0

y = 0

d = 0

# Iterate from 0 to R*C-1
for i in range(m*n):

# Add the current element to the spiral
       
spiral.append(matrix[x][y])
visit[x][y] = True

# Move the pointer to the next position
nr = x + dr[d]
nc = y + dc[d]

# Check if the pointer is at the edge of the matrix and rotate its direction accordingly
if (0 <= nr and nr < m and 0 <= nc and nc < n and not (visit[nr][nc])):
x = nr
y = nc
else:
d = (d+1)%4
x += dr[d]
y += dc [d]
Returns the spiral form

# Call the function and pass it a 2-D matrix
matrix = [[1,2,3,4]，
    [5,6,7,8]，
    [9,10,11,12]，
    [13,14,15,16]]
print("The result is:", end = "")
# Print the elements of the resulting array
for x in spiralform(matrix):
　　print(x, end = "")

Output

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Time Complexity: The time complexity of this method is O(m×n). This is because we are looping over every element of the matrix. As the number of elements increases, the time complexity increases.

Auxiliary Space: Because the queried matrix is stored within another matrix and we also use matrix visit, this method requires O(N) additional memory space.

Solving the Problem by Dividing the Matrix into Cycles

Here’s the approach we’ll follow:
We’ll solve this problem by dividing the given matrix into cycles, or bounds. As we can see from the example above, the outer loop items are stored first, in a clockwise fashion, followed by the inner loop items. Therefore, we can use four loops to print all the loop items. Each loop will be used to traverse the matrix in a specific direction. The first loop will move from the left to the right. However, the second loop will traverse from top to bottom, the third will traverse from right to left, and the final loop will traverse from bottom to top.

Here’s a step-by-step implementation of this method:

• We’ll begin by creating and initializing variables. The variable k will represent the starting row index, m will represent the ending row index, l will represent the starting column index, and n will represent the ending column index.
• We will loop until every square has been printed.
• In each pass of the outer loop, print the elements of the square in clockwise order.
• First, print the entire top row. But for subsequent rows represented by k, only print the elements with columns l through n in row k. Increment k on each pass.
• Print the entire right or last column from top to bottom. For subsequent top-down passes of the (n – 1) column, print the elements from row k to row m. Decrease n on each pass.
• Print the entire bottom row. For rows where k < m, i.e., row (m – 1), print the items from columns n – 1 to l. Decrease m on each pass.
• Now for the left column, if l is less than n, print the items of column l from row index (m – 1) to k. Increment l in each pass.

Now we will implement this method in Python:

Code

#Python program to divide a matrix into loops and print a spiral form

#Define the function that will take input as a 2D list and print the spiral form
def spiralform(matrix):
''' k - starting index of row
m - last row index
l - starting index of column
n - last column index '''
k = 0
m = len(matrix)
l = 0
n = len(matrix[0])

# Start the loop and stop when k > m or l > n
while (k < m and l < n):

# In the remaining columns, print the first row from the unvisited rows first.
for i in range(l, n):
print(matrix[k][i], end = " ")

k = k + 1

# Print the rightmost column of the remaining rows

for i in range(k, m):
print(matrix[i][n - 1], end = " ")

n = n - 1

# Print the last row of the remaining rows, for the remaining columns
if (k < m):

for i in range(n - 1, (l - 1), -1):
print(matrix[m - 1][i], end = " ")

m = m - 1

# Print the leftmost column of the remaining columns
if (l < n):

for i in range(m - 1, k - 1, -1):
print(matrix[i][l], end = " ")

l = l + 1

# Call the function and pass it the matrix
matrix = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]]

spiralform(matrix)

Yield

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Time Complexity:This method has a time complexity of O(m x n). This is because we are looping over every element of the matrix.

Auxiliary Space:This method requires O(1) additional memory space. We are only creating additional integer variables.

Solving the Problem Using Recursion

Here’s our approach:

We’ll solve this problem by using a recursive function to print the edges of the matrix. In each recursive call, we’ll reduce the dimensions of the matrix. We’ll follow the same logic we used in the previous solution.
Here’s a step-by-step approach to this approach:

• We’ll create a recursive function that takes a matrix and the following variables:
• Create a recursive function that takes a matrix and some variables as parameters: k – the start of a row, m – the last row index, l – the start of a column, and n – the last column index.
• Check the basic condition: the starting row and column indices during recursion should be less than the ending row and column indices. Each recursion prints the elements on the edge of the matrix in a clockwise direction.
• Print the top row completely first. But for subsequent rows represented by k, only print the elements of the columns at indices l through n in row k. Increment the count of k on each pass.

  Print the entire right or last column from top to bottom. For the subsequent top-down pass, i.e., the (n-1)th column, print the items from rows k to m. Decrease n on each pass.

  Print the entire bottom row. For rows where k < m, i.e., the (m-1)th row, print the items from columns n-1 to l. Decrease m on each pass. If l < n, then for the left column, print the items from row (m-1) to index position k in column l. Increment l on each pass. Call the function, passing the updated k, m, l, and n values along with the matrix.

Now we will implement this method in Python:

Code

# Python3 program to print the spiral form of the matrix using recursion

# Defining the function which will take a 2-D list and other mentioned variables as input and print the spiral form
def spiralForm(matrix, k, m, l, n):

    ''' k - beginning of the row
        m - last row index
        l - beginning of the column
        n - last column index '''

    # If the lower indices pass the maximum value, the function will stop
    if (k >= m or l >= n):
        return

    # Printing the first row of the remaining rows
    for i in range(l, n):
        print(matrix[i][i], end = " ")

    # Printing the lst column of the remaining columns
    for i in range(k + 1, m):
        print(matrix[i][n - 1], end = " ")

    # Printing the last row only if the remaining first and the last rows are not the same
    if ((m - 1) != k):
        for i in range(n - 2, l - 1, -1):
            print(matrix[m - 1][p], end=" ")

    # Printing the first remaining column if the remaining last and first column are not the same
    if ((n - 1) != l):
        for i in range(m - 2, k, -1):
            print(matrix[i][l], end = " ")

    spiralForm(matrix, k + 1, l + 1, m - 1, n - 1)

# Calling the function and passing the matrix to it

matrix = [[1, 2, 3, 4],
          [5, 6, 7, 8],
          [9, 10, 11, 12],
[13, 14, 15, 16]]
k = 0
m = len(matrix)
l = 0
n = len(matrix[0])

# Function Call
spiralForm(matrix, k, m, l, n)

Output

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Time Complexity Analysis:This method has a time complexity of O(m x n). Because we are looping over every element of the matrix.

Space Complexity Analysis:This method requires only an additional integer variable, so it requires O(1) additional memory space.

Solving the Problem Using DFS

Here’s the idea we’ll use to solve it:

Another recursive way to solve this problem is by considering a DFS move through a given square matrix. A DFS move is: go right, then down, then left, then up, then right again, and continue this move until the last element (the middle element) of the matrix is reached.
We’ll modify the matrix in-place so that as the DFS algorithm pointer visits each matrix cell, the algorithm changes its value to a value that the matrix cannot contain. When the pointer reaches a cell, the algorithm will know that all surrounding cells have forbidden values, or simply, have already been visited, and the DFS algorithm will end its iteration. We’ll create a variable to control the direction of the pointer.

Here’s a step-by-step approach to implementing this method:

• We’ll first create a DFS function that takes a matrix, a cell index, and a direction initializer.
• The algorithm will begin by checking the cell at a given index. A valid cell is one that has not been visited by the pointer. If a cell is invalid, the pointer skips over it and moves on to the next cell.

  If the cell is valid, its value is printed.

  Since the pointer has already visited the cell, we mark it by changing its value to a value not supported by the matrix.

  Next, we need to check if the surrounding cells are valid or if the previous cell is the last one. If so, the algorithm stops. If not, the algorithm continues in the given direction. Assuming the given direction is right, the pointer moves right and checks if the cell is valid. If not, the algorithm changes direction as described above, pointing downward.

  If the cells in that direction are valid, they are printed and marked as visited. If the cells are invalid or the pointer has reached the boundary of the matrix, the pointer’s direction is changed to the left.

  Then repeat the same steps. Check if the cells are valid. If so, print them and mark them as visited. If not, or if the pointer has reached the boundary of the cell, change the direction to upward.

• When the pointer reaches a cell, the process iterates until all surrounding cells have been visited and there are no more cells to print.

We will implement this method in Python

Code

# Python program to print the spiral form of a matrix using DFS recursion

# Define the bounds of the matrix
def isInBounds(k, m, l, n):
if (k < 0 or k >= m or l < 0 or l >= n):
return False
return True

# Define a function to check if a cell is valid
def notValid(matrix, k, m, l, n):

spiral = []

if (not isInBounds(k, m, l, n)):
return True
if (matrix[k][l] == -1):
return True

return False

# Define a function to perform the DFS algorithm
def spiralForm(matrix, k, m, l, n, d, spiral):

# Check if the cell at the given index is valid
if (notValid(matrix, k, m, l, n)):
return

Blocked = True

# Shift right and block access to the cell
for i in range(-1, 2, 2):
Blocked = Blocked and notValid(matrix, i + k, m, l, n) and notValid(matrix, k, m, i + l, n)

# Append the cell shifted right to the result
spiral.append(matrix[k][l])
matrix[k][l] = -1
if (Blocked):
return

# Direction labels used here: 0 for right, 1 for down, 2 for left, 3 for up
nxt_k = k
nxt_l = l
nxt_d = d

# Move right and update direction accordingly
if (d == 0):
if (not notValid(matrix, k, m, l + 1, n)):
nxt_l += 1
else:
nxt_d = 1
nxt_k += 1

# Move down
elif(d == 1):
if (not notValid(matrix, k + 1, m, l, n)):
nxt_k += 1
else:
nxt_d = 2
nxt_l -= 1

# Move left
elif(d == 2):
if (not notValid(matrix, k, m, l - 1, n)):
nxt_k -= 1
else:
nxt_d = 3
nxt_k -= 1

# Move up
elif(d == 3):
if (not notValid(matrix, k - 1, m, l, n)):
nxt_k -= 1
else:
nxt_d = 0
nxt_l += 1

# Recursively call the function and pass the updated matrix, direction, and result list
spiralForm(matrix, nxt_k, m, nxt_l, n, nxt_d, spiral)

# Traverse the matrix
def spiralTraverse(matrix):
spiral = []
spiralForm(matrix, 0, len(matrix), 0, len(matrix[0]), 0, spiral)
return spiral

# Call the function and pass the following matrix
matrix = [[1, 2, 3, 4],
[5, 6, 7, 8], 
[9, 10, 11, 12], 
[13, 14, 15, 16]]

result = spiralTraverse(matrix)
print(result)

Output

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Time Complexity: The time complexity of this algorithm is also O(m x n). This is because we are traversing each element of the matrix one by one.

Space Complexity: This algorithm will use O(1) memory space. Apart from the stack used for recursion, this algorithm does not use any additional memory space.

We have seen various ways to print the spiral form of a matrix. All methods have a time complexity of O(m x n) and require the same O(1) memory space. There may be more ways to solve this problem, but the most basic ones are discussed here.