Spiral Traversal Of A Matrix In Python

Last Updated on June 5, 2023 by Mayank Dham

The traversal of a matrix is a common operation in many programming tasks. The spiral traversal is a specific traversal pattern in which the elements of the matrix are visited in a spiral-like order, beginning at the top-left corner and moving clockwise until all elements are visited. In this article, we will look at various algorithms and provide Python code examples for the spiral traversal of a matrix.

What is a matrix spiral traversal?
Spiral traversal of a matrix is a method of visiting the elements of a two-dimensional matrix in a spiral-like order, beginning at the top-left corner and moving clockwise until all elements have been visited.

Example of spiral matrix in Python:

The preceding example shows how we can traverse the matrix in a spiral fashion. So, in order to solve this problem, we will primarily discuss four approaches:

1. Iterative procedure
2. Recursive strategy
3. Using the DFS method
4. Using a deque

Method 1 : Iterative Approach to solve spiral traversal of a matrix in Python

1. To keep track of the spiral’s boundaries, initialize four variables: top, bottom, left, and right.
2. Create an empty list,’result,’ to hold the visited elements.
3. Create a while loop that runs until ‘top = bottom’ and ‘left = right’.
4. Go through the top row from left to right, appending ‘result’ to each element.
5. Increase the value of ‘top’ by one to exclude the top row from future iterations.
6. Go down the right column from top to bottom, appending ‘result’ to each element.
7. Increase the value of ‘right’ by one to exclude the right column from future iterations.
8. Before proceeding, ensure that ‘top = bottom’ and ‘left = right’.
9. Go down the bottom row from right to left, appending ‘result’ to each element.
10. Increase the value of ‘bottom’ by one to exclude the bottom row from future iterations.
11. Traverse the left column from bottom to top, appending each element to result.
12. Increase ‘left’ by one to remove the left column from subsequent iterations.
13. Display the result list.

Python code for the iterative approach:

def spiral_traversal(matrix):
    top = 0
    bottom = len(matrix) - 1
    left = 0
    right = len(matrix[0]) - 1
    result = []

    while top <= bottom and left <= right:
        for i in range(left, right + 1):
            result.append(matrix[top][i])
        top += 1
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1

        if top <= bottom and left <= right:
           
            for i in range(right, left - 1, -1):
                result.append(matrix[bottom][i])
            bottom -= 1

            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1
    return result

Method 2: Recursive Approach to solve spiral traversal of a matrix in Python

1. Initialize four variables: top, bottom, left, and right to keep track of the boundaries of the spiral.
2. Initialize an empty list, result, to store the visited elements.
3. Define a recursive function, spiral_traversal_recursive(matrix, top, bottom, left, right, result).
4. Base case: If top > bottom or left > right, return.
5. Traverse the top row from left to right, appending each element to result.
6. Increment top by 1.
7. Traverse the right column from top to bottom, appending each element to result.
8. Decrement right by 1.
9. Traverse the bottom row from right to left, appending each element to result.
10. Decrement bottom by 1.
11. Traverse the left column from bottom to top, appending each element to result.
12. Increment left by 1.
13. Recursively call `
14. Call spiral_traversal_recursive(matrix, top, bottom, left, right, result) initially.
15. Return the result list.

Python code for the recursive approach:

def spiral_traversal_recursive(matrix, top, bottom, left, right, result):
    if top > bottom or left > right:
        return
    for i in range(left, right + 1):
        result.append(matrix[top][i])
    top += 1

    for i in range(top, bottom + 1):
        result.append(matrix[i][right])
    right -= 1

    if top <= bottom:
        for i in range(right, left - 1, -1):
            result.append(matrix[bottom][i])
        bottom -= 1
    if left <= right:
        for i in range(bottom, top - 1, -1):
            result.append(matrix[i][left])
        left += 1

    spiral_traversal_recursive(matrix, top, bottom, left, right, result)

def spiral_traversal(matrix):
    result = []
    spiral_traversal_recursive(matrix, 0, len(matrix) - 1, 0, len(matrix[0]) - 1, result)
    return result

Method 3: DFS Approach to solve spiral traversal of a matrix in Python

1. Create a DFS function that takes matrix, cell indices, and direction
2. Checks are cell indices pointing to a valid cell (that is, not visited and in bounds)? if not, skip this cell
3. Print cell value
4. Mark matrix cell pointed by indicates as visited by changing it to a value not supported in the matrix
5. Check are surrounding cells valid? if not stop the algorithm, else continue
6. If the direction is given right then check if the cell to the right is valid. if so, DFS to the right cell given the steps above, else, change the direction to down and DFS downwards given the steps above
7. Else, if the direction given is down then check, if the cell to the down is valid. if so, DFS to the cell below given the steps above, else, change the direction to left and DFS leftwards given the steps above
8. Else, if the direction given is left then check, if the cell to the left is valid. if so, DFS to the left cell given the steps above, else, change the direction to up and DFS upwards given the steps above
9. Otherwise, if the direction given is up then check if the cell to the up is valid. if so, DFS to the upper cell given the steps above, else, change the direction to right and DFS rightwards given the steps above

Python code for the DFS approach:

R = 4
C = 4

def isInBounds(i, j):
    global R
    global C
    if (i < 0 or i >= R or j < 0 or j >= C):
        return False
    return True

def isBlocked(matrix, i, j):
    if (not isInBounds(i, j)):
        return True
    if (matrix[i][j] == -1):
        return True

    return False

def spirallyDFSTraverse(matrix, i, j, Dir, res):
    if (isBlocked(matrix, i, j)):
        return

    allBlocked = True
    for k in range(-1, 2, 2):
        allBlocked = allBlocked and isBlocked(
            matrix, k + i, j) and isBlocked(matrix, i, j + k)

    res.append(matrix[i][j])
    matrix[i][j] = -1
    if (allBlocked):
        return

    # dir: 0 - right, 1 - down, 2 - left, 3 - up
    nxt_i = i
    nxt_j = j
    nxt_dir = Dir
    if (Dir == 0):
        if (not isBlocked(matrix, i, j + 1)):
            nxt_j += 1
        else:
            nxt_dir = 1
            nxt_i += 1

    elif(Dir == 1):
        if (not isBlocked(matrix, i + 1, j)):
            nxt_i += 1
        else:
            nxt_dir = 2
            nxt_j -= 1

    elif(Dir == 2):
        if (not isBlocked(matrix, i, j - 1)):
            nxt_j -= 1
        else:
            nxt_dir = 3
            nxt_i -= 1

    elif(Dir == 3):
        if (not isBlocked(matrix, i - 1, j)):
            nxt_i -= 1
        else:
            nxt_dir = 0
            nxt_j += 1

    spirallyDFSTravserse(matrix, nxt_i, nxt_j, nxt_dir, res)

def spirallyTraverse(matrix):
    res = []
    spirallyDFSTravserse(matrix, 0, 0, 0, res)
    return res

if __name__ == "__main__":
    a = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]

    # Function Call
    res = spirallyTraverse(a)
    print(*res)

Method 4: Using deque to solve spiral traversal of a matrix in Python

1. Begin by setting the matrix’s boundaries to: ‘top’ = 0, ‘bottom’ = rows – 1, ‘left’ = 0, ‘right’ = columns – 1.
2. Create an empty deque,’result,’ in which to store the visited elements in spiral order.
3. Repeat until ‘top = bottom’ and ‘left = right’.
4. From ‘left’ to ‘right,’ traverse the top row of the matrix, appending each element to the ‘result’ deque.
5. Increase the value of ‘top’ by one to exclude the top row from future iterations.
6. From ‘top’ to ‘bottom,’ traverse the right column of the matrix, appending each element to the ‘result’ deque.
7. Decrement right by 1 to exclude the right column from future iterations.
8. Before proceeding, ensure that ‘top = bottom’ and ‘left = right’.
9. Traverse the matrix’s bottom row from ‘right’ to ‘left,’ appending each element to the ‘result’ deque.
10. Decrement bottom by 1 to exclude the bottom row from future iterations.
11. Traverse the left column of the matrix from bottom to top, appending each element to the result deque.
12. Increment left by 1 to exclude the left column from future iterations.
13. Return the elements of the result deque as the spiral traversal of the matrix.

Python code for the deque approach:

from collections import deque

def spiral_traversal(matrix):
    if not matrix:
        return []

    rows, cols = len(matrix), len(matrix[0])
    top, bottom, left, right = 0, rows - 1, 0, cols - 1
    result = deque()

    while top <= bottom and left <= right:
        for i in range(left, right + 1):
            result.append(matrix[top][i])
        top += 1

        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1

        if top <= bottom:
            for i in range(right, left - 1, -1):
                result.append(matrix[bottom][i])
            bottom -= 1

        if left <= right:
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1

    return list(result)

Conclusion
A matrix spiral traversal is a useful technique in a variety of programming scenarios. In this article, we discussed two approaches: iterative and recursive. The iterative approach iterates through the matrix using a while loop, whereas the recursive approach traverses the elements using a helper function. You can efficiently perform a spiral traversal of a matrix and retrieve the elements in the desired order by implementing the provided algorithms in Python.

Frequently Asked Questions (FAQs)

Q1 What are the advantages of using a deque for spiral traversal?
When traversing the matrix in a spiral pattern, using a deque allows for efficient insertion and deletion at both ends, which is advantageous. It allows you to append elements from all sides without having to manage indexes manually.

Q2. Could you explain the distinction between iterative and recursive approaches?
The iterative approach traverses the matrix in a spiral pattern using loops and boundary variables, whereas the recursive approach uses a recursive function with updated boundaries to achieve the same result. Personal preference and specific programming requirements dictate which approach is used.

Q3. What if the matrix is empty or has incorrect dimensions?
Both the iterative and recursive approaches will return an empty result if the matrix is empty. For invalid dimensions, the behavior may vary depending on the implementation. For proper traversal, it is generally assumed that the matrix has valid dimensions.

Q4. How do I incorporate the spiral traversal algorithm into my own code?
To use the spiral traversal algorithm in your code, define the appropriate function (iterative or recursive) and pass your matrix as an argument. The function will return a list or deque containing the matrix elements in spiral order, which you can then process as necessary.