Spiral Traversal on a Matrix

Understanding the Problem

The goal is to traverse a matrix in a spiral order.

Method 1: Using Iterative Approach

This method uses an iterative approach to traverse the matrix in spiral order.

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

    while top <= bottom and left <= right:
        # Traverse from left to right
        for i in range(left, right + 1):
            print(matrix[top][i], end=" ")
        top += 1

        # Traverse from top to bottom
        for i in range(top, bottom + 1):
            print(matrix[i][right], end=" ")
        right -= 1

        if top <= bottom:
            # Traverse from right to left
            for i in range(right, left - 1, -1):
                print(matrix[bottom][i], end=" ")
            bottom -= 1

        if left <= right:
            # Traverse from bottom to top
            for i in range(bottom, top - 1, -1):
                print(matrix[i][left], end=" ")
            left += 1

    print()  # New line after traversal

# Example usage
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
]
print("Spiral Traversal: ", end="")
spiral_traversal(matrix)

Output:

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

Method 2: Using Recursion

This method uses recursion to achieve spiral traversal.

def spiral_util(matrix, top, bottom, left, right):
    if top > bottom or left > right:
        return

    # Traverse from left to right
    for i in range(left, right + 1):
        print(matrix[top][i], end=" ")
    top += 1

    # Traverse from top to bottom
    for i in range(top, bottom + 1):
        print(matrix[i][right], end=" ")
    right -= 1

    if top <= bottom:
        # Traverse from right to left
        for i in range(right, left - 1, -1):
            print(matrix[bottom][i], end=" ")
        bottom -= 1

    if left <= right:
        # Traverse from bottom to top
        for i in range(bottom, top - 1, -1):
            print(matrix[i][left], end=" ")
        left += 1

    # Recursive call for the next layer
    spiral_util(matrix, top, bottom, left, right)

def spiral_traversal(matrix):
    spiral_util(matrix, 0, len(matrix) - 1, 0, len(matrix[0]) - 1)
    print()  # New line after traversal

# Example usage
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
]
print("Spiral Traversal: ", end="")
spiral_traversal(matrix)

Output:

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