Python Program to Print a Spiral Matrix

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

Sample Inputs and Outputs to Understand 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

Solving the Problem Using the Simulation Approach

We will follow this idea to solve the problem using a simulation approach:

We will draw the spiral path for a given matrix or 2D array. The spiral path has to move in a clockwise direction. It will change the path or make turns at the edges only so that the loop does not go out of the bounds of the matrix.

Below are the steps to be followed:

Let the matrix have m number of rows and n number of columns.
Visited[m] will denote the cell of the m-th row and n-th columns, which we have already visited. Our current position in the matrix is denoted by (m, n). It will have direction d, and we have to traverse through the total m x n cells.
As we will continue the traversal, the next position of the pointer will be represented by (nr, nc)
If the pointer is on the cell which is at the bounds of the matrix and yet unseen, then it will make a clockwise 90-degree turn, and it will become the next position of the pointer, i.e., (nr, nc)

Now we will implement this approach in Python.

Code

# Python program to print the spiral form of the matrix using the simulation approach
  
# Defining the function that will take a matrix and will return its spiral form
def spiralform(matrix):
    spiral = []

    # If there are no elements in the matrix, it will return an empty array
    if (len(matrix) == 0):
        return spiral

    # Storing the number of rows m and the number of columns n of the matrix
    m = len(matrix)
    n = len(matrix[0])

    # Creating an empty matrix of the same size
    visit = [[0 for i in range(n)] for j in range(m)]

    # Intializing the direction vectors and coordinated
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    x = 0
    y = 0
    d = 0
  
    # Iterating from 0 to R * C - 1
    for i in range(m * n):

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

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

        # Checking if the pointer is at the edge of the matrix and hence rotating its direction
        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]
    return spiral
  
  
# Calling the function and passing a 2-D matrix to the function
matrix = [[1, 2, 3, 4],
      [5, 6, 7, 8],
      [9, 10, 11, 12],
      [13, 14, 15, 16]]

# Printing the elements of the resultant 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 approach is O(m x n). This is because we are going through each element of the matrix. As the number of elements will increase, the time complexity will also increase.

Auxiliary Space: Since the resultant matrix is stored in another matrix and also we have used the matrix visit, this approach takes O(N) extra memory space.

Solving the Problem by Dividing the Matrix into Cycles

This is the idea that we will follow to solve the problem:

We will solve this problem by dividing the given matrix into loops or boundaries. We can see from the above examples that the outer loop items are first stored clockwise, and then the inner loop items are stored. So we can print all the loop items using four for loops. Each for loop will work for traversal in a particular direction. The first loop will move from the left of the matrix to the right. However, the second loop will move from the top to the bottom, the third one will traverse the matrix from right to left, and the last loop will move from bottom to up.

Following is the step-by-step approach for the implementation of this method:

We will start by creating and initializing the variables. The variable k will represent starting of the row index, m will represent the ending of a particular row, l will represent the starting of a column, and n will represent the ending of the column index.
We will run the loop until each square is printed.
In each outer loop traversal, print the elements of a square clockwise.
Firstly completely print the top row. But for subsequent rows denoted by k, print only elements of the column from index l to n for the kth row. Increase the count of k at each traversal.
Print the complete right or the last column from top to bottom. For the subsequent top to down traversal, i.e., for (n - 1)th column, print the items from the row k to m. Decrease n by 1 at each traversal.
Print the complete bottom row. For the rows k < m, i.e., (m - 1)th row, print the items from the column n - 1 to l. Decrease m by 1 at each traversal.
Now for the left column, if l is less than n, print the items of the lth column from row index (m - 1) to k. Increase l by 1 at each traversal.

Now we will implement this method in Python:

Code

# Python program to print the spiral form of the matrix by dividing the matrix into cycles
  
# Defining the function which will take the 2-D list as input and print the spiral form
def spiralform(matrix):
    ''' k - beginning of the row
        m - last row index
        l - beginning of the column
        n - last column index '''
    k = 0
    m = len(matrix)
    l = 0
    n = len(matrix[0])

    # Starting the loop with the condition to stoop the loop when k > m and l > n
    while (k < m and l < n):
  
        # Printing the first row out of the unvisited rows from the remaining columns
        for i in range(l, n):
            print(matrix[k][i], end = " ")
  
        k = k + 1
  
        # Printing the rightmost column out of the remaining columns for the remaining rows
        for i in range(k, m):
            print(matrix[i][n - 1], end = " ")
  
        n = n - 1
  
        # Printing the last row from 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
  
        # Printing the leftmost column out of the remaining columns
        if (l < n):
            for i in range(m - 1, k - 1, -1):
                print(matrix[i][l], end = " ")
  
            l = l + 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]]

spiralform(matrix)

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 x n). This is because we are traversing through each element of the matrix.

Auxiliary Space: This method takes O(1) extra memory space. We have just created extra integer variables.

Solving the Problem Using Recursion

This is the idea that we will follow to solve the problem:

We will solve this problem by printing the edges of the matrix using a recursion function. In every recursive call, we will decrease the dimensions of the matrix. We will follow the same logic we used in the previous solution.

Following is the step-by-step approach for the implementation of this method:

We will create a recursive function that will take the matrix and the following variables
Create a recursive function that takes a matrix and some variables, k - beginning of the row, m - last row index, l - beginning of the column, n - last column index, as parameters.
Checking the base condition, starting indices of the row and column should be every recursion less than the ending indices of the row and column, respectively. The function at each recursion will print the elements present at the edges of the matrix in a clockwise manner.
Firstly completely print the top row. But for subsequent rows denoted by k, print only elements of the column from index l to n for the kth row. Increase the count of k at each traversal.
Print the complete right or the last column from top to bottom. For the subsequent top to down traversal, i.e., for (n - 1)th column, print the items from the row k to m. Decrease n by 1 at each traversal.
Print the complete bottom row. For the rows k < m, i.e., (m - 1)th row, print the items from the column n - 1 to l. Decrease m by 1 at each traversal.
Now for the left column, if l is less than n, print the items of the lth column from row index (m - 1) to k. Increase l by 1 at each traversal.
Call the function and pass the updated values of k, m, l, n along with the matrix to the function.

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: The time complexity of this method is O(m x n). This is because we are traversing through each element of the matrix.

Auxiliary Space: This method takes O(1) extra memory space. We have just created extra integer variables.

Solving the Problem UsingDFS

This is the idea that we will follow to solve the problem:

Another recursive way to solve this problem is by considering DFS movement within the given square matrix. The DFS movement is: going right, then down, then left, then up, then again right, and continuing this movement until we have reached the last element (the middlemost element) of the matrix.

We will modify the matrix in-place so that when the DFS algorithm pointer visits every matrix cell, the algorithm will change its value to a value the matrix cannot contain. The DFS algorithm will end the iteration when it reaches a cell when all of its surrounding cells have the value forbidden to go to or, in simple words, have already visited before. We will create a variable that will control the direction of the pointer.

Following is the step-by-step approach for the implementation of this method:

We will start by creating a DFS function which will take a matrix, indices of the cells, and the direction initializer.
The algorithm will start by checking that the cell of the index given is valid. A valid cell is one that is not visited by the pointer before. If the cell is not valid, the pointer will skip this cell and goes to the next cell.
If the cell is valid, we will print its value.
Since the pointer has visited this cell, we will mark it by changing its value to something the matrix will not support.
Then we need to check if the surrounding cells are valid or if the previous cell was the last. If yes, then stop the algorithm. If no, then the algorithm will continue in the direction given as the argument. Suppose the direction given is right; the pointer will move toward the right and check if the cell is valid. If not, the algorithm will change the direction as specified above. It will point downwards.
If the cell in this direction is valid, then print those cells and mark them as visited. If the cells are not valid or the pointer has reached the matrix boundary, the pointer will change its direction to the left.
Then repeat the same steps. Check if cells are valid. If yes, then print them and mark them visited. If no, or the pointer has reached the boundary of the cell, change the direction to up.
The algorithm will repeat the same steps in the upward direction. Printing valid cells and marking them visited. If the cells are invalid, the pointer will change its direction to the right again.
This process will go on iteratively once the pointer has reached a cell when all surrounding cells are visited, and no more cell is left to print.

We will implement this approach in Python

Code

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

# Defining 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
  
# Defining a function to check if the cell is valid or not
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
  
# Defining the function to execute the DFS algorithm
def spiralForm(matrix, k, m, l, n, d, spiral):

    # Check if the given indices' cell is valid or not
    if (notValid(matrix, k, m, l, n)):
        return

    Blocked = True

    # Traversing in the right direction and blocking the visited cells
    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)

    # Adding cells in the right direction to the result
    spiral.append(matrix[k][l])
    matrix[k][l] = -1
    if (Blocked):
        return
  
    # direction labels used here: 0 is for right, 1 is for down, 2 is for left, 3 is for up
    nxt_k = k
    nxt_l = l
    nxt_d = d

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

    # Traversing in a downwards direction
    elif(d == 1):
        if (not notValid(matrix, k + 1, m, l, n)):
            nxt_k += 1
        else:
            nxt_d = 2
            nxt_l -= 1

    # Traversing in the left direction
    elif(d == 2):
        if (not notValid(matrix, k, m, l - 1, n)):
            nxt_k -= 1
        else:
            nxt_d = 3
            nxt_k -= 1
    
    # Traversing in the upward direction
    elif(d == 3):
        if (not notValid(matrix, k - 1, m, l, n)):
            nxt_k -= 1
        else:
            nxt_d = 0
            nxt_l += 1

    # Calling the function recursively and passing the updated matrix, directions, and resultant list
    spiralForm(matrix, nxt_k, m, nxt_l, n, nxt_d, spiral)
 
# Traversing the matrix 
def spiralTraverse(matrix):
    spiral = []
    spiralForm(matrix, 0, len(matrix), 0, len(matrix[0]), 0, spiral)
    return spiral
 
# Calling the function and passing 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: This algorithm also has O(m x n) time complexity. This is because we are traversing through each element of the matrix individually.

Auxiliary Space: This algorithm will take O(1) memory space. Except for the stack used by recursion, this algorithm uses no extra memory space.

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

Next TopicPython with Qt Designer: Quicker GUI Application Development

← prev next →