{"id":4591,"date":"2024-10-21T11:04:44","date_gmt":"2024-10-21T11:04:44","guid":{"rendered":"https:\/\/algocademy.com\/blog\/matrix-traversal-mastering-spiral-diagonal-and-zigzag-patterns\/"},"modified":"2026-10-15T10:34:50","modified_gmt":"2026-10-15T10:34:50","slug":"matrix-traversal-mastering-spiral-diagonal-and-zigzag-patterns","status":"publish","type":"post","link":"https:\/\/algocademy.com\/blog\/matrix-traversal-mastering-spiral-diagonal-and-zigzag-patterns\/","title":{"rendered":"Matrix Traversal: Spiral, Diagonal and Zigzag Patterns in Python"},"content":{"rendered":"

Matrix traversal problems ask you to visit every cell of a 2D grid in a specific order. Spiral order uses four shrinking boundaries, diagonal order groups cells by row + col<\/code>, and zigzag order is diagonal order with every other diagonal reversed. Each runs in O(rows x cols) time, and the bugs almost always come from non-square matrices, a single row or column, and off-by-one boundaries.<\/p>\n

All examples are Python. They share this 3×4 test matrix, and the outputs shown were produced by running the code:<\/p>\n

m = [[1,  2,  3,  4],\n     [5,  6,  7,  8],\n     [9, 10, 11, 12]]\n<\/code><\/pre>\n
Spiral order<\/h2>\n
Walk the outer ring clockwise, then repeat on the ring inside. Track four boundaries (top<\/code>, bottom<\/code>, left<\/code>, right<\/code>) and move each one inward after you finish the side it controls.<\/p>\n
def spiral(matrix):\n    if not matrix or not matrix[0]:\n        return []\n    out = []\n    top, bottom = 0, len(matrix) - 1\n    left, right = 0, len(matrix[0]) - 1\n    while top <= bottom and left <= right:\n        for c in range(left, right + 1):          # left to right along the top\n            out.append(matrix[top][c])\n        top += 1\n        for r in range(top, bottom + 1):          # down the right side\n            out.append(matrix[r][right])\n        right -= 1\n        if top <= bottom:                         # right to left along the bottom\n            for c in range(right, left - 1, -1):\n                out.append(matrix[bottom][c])\n            bottom -= 1\n        if left <= right:                         # up the left side\n            for r in range(bottom, top - 1, -1):\n                out.append(matrix[r][left])\n            left += 1\n    return out\n\nprint(spiral(m))   # [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]\n<\/code><\/pre>\n
The two if<\/code> checks are the part that matters. After the top row and right column are done, the remaining ring may have collapsed into a single row or column (for example the middle row of a 3-row matrix). Without the checks, you would walk that row a second time in the opposite direction and output duplicates. Test [[1,2,3]]<\/code>, [[1],[2],[3]]<\/code> and a 3×4 matrix like the one above.<\/p>\n
The direction-vector alternative<\/h3>\n
If boundary bookkeeping feels fragile, simulate a walker instead: keep going in the current direction, and turn right when the next cell is out of bounds or already visited.<\/p>\n
def spiral_dirs(matrix):\n    if not matrix or not matrix[0]:\n        return []\n    R, C = len(matrix), len(matrix[0])\n    seen = [[False] * C for _ in range(R)]\n    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]    # right, down, left, up\n    r = c = d = 0\n    out = []\n    for _ in range(R * C):\n        out.append(matrix[r][c])\n        seen[r][c] = True\n        nr, nc = r + dirs[d][0], c + dirs[d][1]\n        if not (0 <= nr < R and 0 <= nc < C) or seen[nr][nc]:\n            d = (d + 1) % 4\n            nr, nc = r + dirs[d][0], c + dirs[d][1]\n        r, c = nr, nc\n    return out\n<\/code><\/pre>\n
This is harder to get wrong but uses O(rows x cols) extra memory for seen<\/code>. I checked that both versions return the same order on 500 random matrices from 1×1 to 7×7. It is a good fallback when you are under time pressure.<\/p>\n
Writing a spiral instead of reading one<\/h3>\n
“Spiral Matrix II” fills an n x n grid with 1..n\u00b2 in spiral order. The boundary code is the same, but you assign instead of append:<\/p>\n
def generate_spiral(n):\n    grid = [[0] * n for _ in range(n)]\n    top, bottom, left, right = 0, n - 1, 0, n - 1\n    k = 1\n    while top <= bottom and left <= right:\n        for c in range(left, right + 1):\n            grid[top][c] = k; k += 1\n        top += 1\n        for r in range(top, bottom + 1):\n            grid[r][right] = k; k += 1\n        right -= 1\n        if top <= bottom:\n            for c in range(right, left - 1, -1):\n                grid[bottom][c] = k; k += 1\n            bottom -= 1\n        if left <= right:\n            for r in range(bottom, top - 1, -1):\n                grid[r][left] = k; k += 1\n            left += 1\n    return grid\n\nprint(generate_spiral(3))   # [[1, 2, 3], [8, 9, 4], [7, 6, 5]]\n<\/code><\/pre>\n
Diagonal order<\/h2>\n
All cells on the same anti-diagonal (running from top-right to bottom-left) share the same value of row + col<\/code>. That gives you a clean way to enumerate them with no special cases: loop over the sum s<\/code> from 0 to rows + cols - 2<\/code>, and for each s<\/code> collect the cells that are inside the grid.<\/p>\n
def diagonals(matrix):\n    if not matrix or not matrix[0]:\n        return []\n    R, C = len(matrix), len(matrix[0])\n    out = []\n    for s in range(R + C - 1):\n        r = max(0, s - (C - 1))        # first row where col = s - r is still inside\n        diag = []\n        while r < R and s - r >= 0:\n            diag.append(matrix[r][s - r])\n            r += 1\n        out.append(diag)\n    return out\n\nprint(diagonals(m))\n# [[1], [2, 5], [3, 6, 9], [4, 7, 10], [8, 11], [12]]\n<\/code><\/pre>\n
For the other direction (top-left to bottom-right), cells share the same value of col - row<\/code>, which ranges from -(R - 1)<\/code> to C - 1<\/code>:<\/p>\n
def main_diagonals(matrix):\n    R, C = len(matrix), len(matrix[0])\n    return [[matrix[r][r + k] for r in range(R) if 0 <= r + k < C]\n            for k in range(-(R - 1), C)]\n\nprint(main_diagonals(m))\n# [[9], [5, 10], [1, 6, 11], [2, 7, 12], [3, 8], [4]]\n<\/code><\/pre>\n
Knowing “same diagonal means same r + c<\/code> or same c - r<\/code>” also solves problems that never mention traversal, such as placing queens in N-Queens (track used diagonals in a set) or grouping cells in “Diagonal Traverse” and “Sort the Matrix Diagonally”.<\/p>\n
Zigzag order<\/h2>\n
Zigzag (the “Diagonal Traverse” problem) visits the same anti-diagonals but alternates direction: the first goes up-right, the next down-left, and so on. Reusing diagonals<\/code>, reverse every other one. The first diagonal has one cell, so the parity does not matter for it, but the second must be read from the bottom up: [5, 2]<\/code>.<\/p>\n
def zigzag(matrix):\n    out = []\n    for s, diag in enumerate(diagonals(matrix)):\n        out.extend(diag if s % 2 else diag[::-1])\n    return out\n\nprint(zigzag(m))   # [1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12]\n<\/code><\/pre>\n
Here diagonals<\/code> lists each diagonal top-to-bottom, so odd-numbered ones are already in down-left order, and even-numbered ones are reversed to go up-right. This version uses O(rows + cols) extra memory per diagonal and is easy to reason about. If you are asked for O(1) extra space, simulate the walk instead:<\/p>\n
def zigzag_walk(matrix):\n    if not matrix or not matrix[0]:\n        return []\n    R, C = len(matrix), len(matrix[0])\n    r = c = 0\n    up = True\n    out = []\n    for _ in range(R * C):\n        out.append(matrix[r][c])\n        if up:\n            if c == C - 1:\n                r += 1; up = False         # hit the right edge: step down, turn around\n            elif r == 0:\n                c += 1; up = False         # hit the top edge: step right, turn around\n            else:\n                r -= 1; c += 1\n        else:\n            if r == R - 1:\n                c += 1; up = True          # hit the bottom edge: step right\n            elif c == 0:\n                r += 1; up = True          # hit the left edge: step down\n            else:\n                r += 1; c -= 1\n    return out\n<\/code><\/pre>\n
The order of the edge checks matters. In the upward direction, check the right edge before the top edge, because in a corner such as the top-right cell you must go down, not right. The same applies in reverse for the bottom and left edges. Swapping these checks is the most common zigzag bug, and it only shows up on non-square matrices or specific corners. The two zigzag versions agree on 500 random matrices in my check.<\/p>\n
Complexity<\/h2>\n\n\n\n\n\n\n\n\n
Pattern<\/th>\nTime<\/th>\nExtra space (besides output)<\/th>\n<\/tr>\n<\/thead>\n
Spiral (boundaries)<\/td>\nO(R x C)<\/td>\nO(1)<\/td>\n<\/tr>\n
Spiral (visited grid)<\/td>\nO(R x C)<\/td>\nO(R x C)<\/td>\n<\/tr>\n
Diagonals by r + c<\/td>\nO(R x C)<\/td>\nO(min(R, C)) per diagonal<\/td>\n<\/tr>\n
Zigzag walk<\/td>\nO(R x C)<\/td>\nO(1)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
You cannot beat O(R x C) when every cell must be visited.<\/p>\n
Common mistakes<\/h2>\n