5 Best Ways to Print Matrix Elements in Spiral Order in Python

5/5 - (1 vote)

πŸ’‘ Problem Formulation: The task is to traverse and print the elements of a 2D array (matrix) in a spiral order, starting from the top-left corner and progressively moving inwards. For instance, given a 3×3 matrix with elements from 1 to 9, the output should be 1 2 3 6 9 8 7 4 5.

Method 1: Layer-by-Layer Traversal

This method processes the matrix in a series of rectangular layers. Each layer represents the next outermost ring of the matrix. The function peels off each layer and prints its elements, starting from the outermost to the innermost layer.

Here’s an example:

def spiralOrder(matrix):
    res = []
    while matrix:
        res += matrix.pop(0)
        matrix = list(zip(*matrix))[::-1]
    return res

# Example usage
matrix = [[1,2,3], [4,5,6], [7,8,9]]
print(spiralOrder(matrix))

Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

This code snippet first initializes an empty list res to hold the elements in spiral order. It then enters a loop where it concatenates the first row of the matrix to res, removes that row, and rotates the matrix counter-clockwise. This action turns the next spiral layer vertically aligned on the top, ready to be popped off in the next iteration.

Method 2: Simulation of Spiral Movement

This approach involves simulating the spiral movement by iterating over the matrix boundaries with carefully adjusted indexing. When the boundary of one direction is traversed, it reduces the corresponding boundary limit and changes the direction accordingly.

Here’s an example:

def spiralOrder(matrix):
    res = []
    while matrix:
        for x in matrix.pop(0): res.append(x)
        for row in matrix:
            if row: res.append(row.pop())
        if matrix and matrix[-1]: res += matrix.pop()[::-1]
        for row in matrix[::-1]:
            if row: res.append(row.pop(0))
    return res
    
# Example usage
matrix = [[1,2,3], [4,5,6], [7,8,9]]
print(spiralOrder(matrix))

Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

The function in this snippet moves right, down, left, and up in this order, and then inward in a loop, appending elements to the result list res. Each boundary traversed is popped from the matrix to avoid revisiting those elements. This continues until all elements have been visited.

Method 3: Directional Iteration

In this method, the traversal is done by maintaining a direction state and updating it as the traversal hits the matrix boundary or already visited cells, ensuring that the traversal is in spiral form.

Here’s an example:

def spiralOrder(matrix):
    if not matrix: return []
    res, m, n = [], len(matrix), len(matrix[0])
    seen = [[False]*n for _ in matrix]
    dr, dc = [0, 1, 0, -1], [1, 0, -1, 0]
    r = c = di = 0
    for _ in range(m * n):
        res.append(matrix[r][c])
        seen[r][c] = True
        cr, cc = r + dr[di], c + dc[di]
        if 0 <= cr < m and 0 <= cc < n and not seen[cr][cc]:
            r, c = cr, cc
        else:
            di = (di + 1) % 4
            r, c = r + dr[di], c + dc[di]
    return res

# Example usage
matrix = [[1,2,3], [4,5,6], [7,8,9]]
print(spiralOrder(matrix))

Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

This code snippet uses two arrays, dr and dc, to capture the direction offsets. By updating the row r and column c index variables using these offsets, it controls the traversal direction. When the next cell to visit is out of bounds or already visited, it changes direction by rotating the direction index di.

Method 4: Recursive Peeling

This solution adopts a recursive approach, peeling off the top row and the rightmost column on each recursive call, then passing the submatrix (without the first row and the last column) back into the function.

Here’s an example:

def spiralOrder(matrix):
    return matrix and [*matrix.pop(0)] + spiralOrder([*zip(*matrix)][::-1])

# Example usage
matrix = [[1,2,3], [4,5,6], [7,8,9]]
print(spiralOrder(matrix))

Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

Exploring recursion, the given code snippet repeatedly removes the first row and appends it to the result. The remaining part of the matrix is then rotated to align the next layer on top. This modified matrix is passed back into the function until the matrix is empty.

Bonus One-Liner Method 5: The Pythonic Way

Leveraging the power of Python, we can achieve the same result with a one-liner that combines list comprehension, unpacking, and the power of the zip function to rotate the matrix.

Here’s an example:

spiralOrder = lambda m: m and [*m.pop(0)] + spiralOrder([*zip(*m)][::-1])

# Example usage
matrix = [[1,2,3], [4,5,6], [7,8,9]]
print(spiralOrder(matrix))

Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

This snippet applies a lambda function, compressing the recursive approach into one line. It uses the splat operator to unpack the rotated submatrix correctly, creating an efficient and elegant solution to the spiral traversal problem.

Summary/Discussion

  • Method 1: Layer-by-Layer Traversal.
    Strengths: Simple and uses matrix transformations. Weaknesses: Mutates original matrix.
  • Method 2: Simulation of Spiral Movement.
    Strengths: Easy to visualize and follow. Weaknesses: Mutates original matrix and might not be as efficient due to dynamic list operations.
  • Method 3: Directional Iteration.
    Strengths: Efficient in both time and space complexity. Weaknesses: More complex logic involving direction control.
  • Method 4: Recursive Peeling.
    Strengths: Simple and elegant recursive solution. Weaknesses: Python’s default recursion limit may be an issue for very large matrices.
  • Bonus Method 5: The Pythonic Way.
    Strengths: Extremely concise. Weaknesses: Readability may suffer due to being a one-liner; still carries recursion limit concerns.