PK

PKBytes

Explore tracks
Chapter 10: Matrices, Grids and Multidimensional Arrays
10.03Beginner / Intermediate5 topics14 min5 interactive animations

Traversal patterns

Classic ways to walk a matrix: spiral, anti-diagonals, zigzag, boundary and snake patterns, each with the loop bounds that make it correct for any rectangle.

Learning goals

  • Write spiral traversal with shrinking bounds
  • Enumerate anti-diagonals by the constant r + c
  • Handle single-row and single-column edge cases

Prerequisites

Basic operations
10.03.1

Spiral traversal

Spiral order peels the outer ring clockwise (top row, right column, bottom row, left column) and then repeats on the shrinking inner matrix. Keep four bounds top, bottom, left, right; after each ring move them inward. The guards top < bottom and left < right stop the last row or column from being visited twice when only one remains.

Run the default 3 × 4 spiral and then try a single row.

Java
1static List<Integer> spiral(int[][] g) {
2    List<Integer> out = new ArrayList<>();
3    int top = 0, bottom = g.length - 1, left = 0, right = g[0].length - 1;
4    while (top <= bottom && left <= right) {
5        for (int c = left; c <= right; c++) out.add(g[top][c]);
6        for (int r = top + 1; r <= bottom; r++) out.add(g[r][right]);
7        if (top < bottom) for (int c = right - 1; c >= left; c--) out.add(g[bottom][c]);
8        if (left < right) for (int r = bottom - 1; r > top; r--) out.add(g[r][left]);
9        top++; bottom--; left++; right--;
10    }
11    return out;
12}

Matrix traversal orders

Interactive · edit the input

Your input

Try

grid · 3 × 4

0123
0
1
2
3
4
1
5
6
7
8
2
9
10
11
12
Visiting nowAlready visited

visit order

none yet
Setup

Spiral: walk the outer ring clockwise, then repeat on the shrinking inner matrix.

Step 1 / 14
Java
1// row-major: consecutive memory, cache friendly
2for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) visit(g[r][c]);
3// column-major: jumps a whole row each step
4for (int c = 0; c < C; c++) for (int r = 0; r < R; r++) visit(g[r][c]);
5// snake: odd rows run right to left
6for (int r = 0; r < R; r++) for (int k = 0; k < C; k++) visit(g[r][r % 2 == 0 ? k : C - 1 - k]);
7// spiral: peel the outer ring, then shrink the bounds
8int top = 0, bottom = R - 1, left = 0, right = C - 1;
9while (top <= bottom && left <= right) {
10    for (int c = left; c <= right; c++) visit(g[top][c]);                       // top side
11    for (int r = top + 1; r <= bottom; r++) visit(g[r][right]);                 // right side
12    if (top < bottom) for (int c = right - 1; c >= left; c--) visit(g[bottom][c]);   // bottom side
13    if (left < right) for (int r = bottom - 1; r > top; r--) visit(g[r][left]);      // left side
14    top++; bottom--; left++; right--;                                           // boundary-only stops after one ring
15}
16// cells with the same r + c form an anti-diagonal; zigzag reverses every other one
17for (int d = 0; d < R + C - 1; d++) {
18    for (int r = Math.max(0, d - C + 1); r <= Math.min(d, R - 1); r++) visit(g[r][d - r]);
19}

Live state

R

3

C

4

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L10R=3 C=4Spiral: walk the outer ring clockwise, then repeat on the shrinking inner matrix.
2L10step=1 r=0 c=0 g[r][c]=1Visit g[0][0] = 1 (cell 1 of 12).
3L10step=2 r=0 c=1 g[r][c]=2Visit g[0][1] = 2 (cell 2 of 12).
4L10step=3 r=0 c=2 g[r][c]=3Visit g[0][2] = 3 (cell 3 of 12).
5L10step=4 r=0 c=3 g[r][c]=4Visit g[0][3] = 4 (cell 4 of 12).
6L10step=5 r=1 c=3 g[r][c]=8Visit g[1][3] = 8 (cell 5 of 12).
7L10step=6 r=2 c=3 g[r][c]=12Visit g[2][3] = 12 (cell 6 of 12).
8L10step=7 r=2 c=2 g[r][c]=11Visit g[2][2] = 11 (cell 7 of 12).
9L10step=8 r=2 c=1 g[r][c]=10Visit g[2][1] = 10 (cell 8 of 12).
10L10step=9 r=2 c=0 g[r][c]=9Visit g[2][0] = 9 (cell 9 of 12).
11L10step=10 r=1 c=0 g[r][c]=5Visit g[1][0] = 5 (cell 10 of 12).
12L10step=11 r=1 c=1 g[r][c]=6Visit g[1][1] = 6 (cell 11 of 12).
13L10step=12 r=1 c=2 g[r][c]=7Visit g[1][2] = 7 (cell 12 of 12).
14L10return=[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]12 cells visited: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]. O(R x C) time.
10.03.2

Diagonals

Cells on the same anti-diagonal (running from top-right to bottom-left) share the same sum r + c. There are R + C - 1 of them, numbered d = 0 to R + C - 2; on diagonal d the row runs from max(0, d - C + 1) to min(d, R - 1) and the column is d - r. Main-direction diagonals share r - c instead.

Choose Anti-diagonals to see the grouping.

Java
1for (int d = 0; d < R + C - 1; d++) {
2    for (int r = Math.max(0, d - C + 1); r <= Math.min(d, R - 1); r++) {
3        visit(g[r][d - r]);       // r + c == d
4    }
5}

Matrix traversal orders

Interactive · edit the input

Your input

Try

grid · 3 × 4

0123
0
1
2
3
4
1
5
6
7
8
2
9
10
11
12
Visiting nowAlready visited

visit order

none yet
Setup

Spiral: walk the outer ring clockwise, then repeat on the shrinking inner matrix.

Step 1 / 14
Java
1// row-major: consecutive memory, cache friendly
2for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) visit(g[r][c]);
3// column-major: jumps a whole row each step
4for (int c = 0; c < C; c++) for (int r = 0; r < R; r++) visit(g[r][c]);
5// snake: odd rows run right to left
6for (int r = 0; r < R; r++) for (int k = 0; k < C; k++) visit(g[r][r % 2 == 0 ? k : C - 1 - k]);
7// spiral: peel the outer ring, then shrink the bounds
8int top = 0, bottom = R - 1, left = 0, right = C - 1;
9while (top <= bottom && left <= right) {
10    for (int c = left; c <= right; c++) visit(g[top][c]);                       // top side
11    for (int r = top + 1; r <= bottom; r++) visit(g[r][right]);                 // right side
12    if (top < bottom) for (int c = right - 1; c >= left; c--) visit(g[bottom][c]);   // bottom side
13    if (left < right) for (int r = bottom - 1; r > top; r--) visit(g[r][left]);      // left side
14    top++; bottom--; left++; right--;                                           // boundary-only stops after one ring
15}
16// cells with the same r + c form an anti-diagonal; zigzag reverses every other one
17for (int d = 0; d < R + C - 1; d++) {
18    for (int r = Math.max(0, d - C + 1); r <= Math.min(d, R - 1); r++) visit(g[r][d - r]);
19}

Live state

R

3

C

4

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L10R=3 C=4Spiral: walk the outer ring clockwise, then repeat on the shrinking inner matrix.
2L10step=1 r=0 c=0 g[r][c]=1Visit g[0][0] = 1 (cell 1 of 12).
3L10step=2 r=0 c=1 g[r][c]=2Visit g[0][1] = 2 (cell 2 of 12).
4L10step=3 r=0 c=2 g[r][c]=3Visit g[0][2] = 3 (cell 3 of 12).
5L10step=4 r=0 c=3 g[r][c]=4Visit g[0][3] = 4 (cell 4 of 12).
6L10step=5 r=1 c=3 g[r][c]=8Visit g[1][3] = 8 (cell 5 of 12).
7L10step=6 r=2 c=3 g[r][c]=12Visit g[2][3] = 12 (cell 6 of 12).
8L10step=7 r=2 c=2 g[r][c]=11Visit g[2][2] = 11 (cell 7 of 12).
9L10step=8 r=2 c=1 g[r][c]=10Visit g[2][1] = 10 (cell 8 of 12).
10L10step=9 r=2 c=0 g[r][c]=9Visit g[2][0] = 9 (cell 9 of 12).
11L10step=10 r=1 c=0 g[r][c]=5Visit g[1][0] = 5 (cell 10 of 12).
12L10step=11 r=1 c=1 g[r][c]=6Visit g[1][1] = 6 (cell 11 of 12).
13L10step=12 r=1 c=2 g[r][c]=7Visit g[1][2] = 7 (cell 12 of 12).
14L10return=[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]12 cells visited: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]. O(R x C) time.
10.03.3

Zigzag traversal

Zigzag (diagonal) traversal walks the anti-diagonals but alternates the direction: even diagonals go up-right, odd ones down-left (or the other way round). It is the anti-diagonal loop with every other diagonal reversed, which also reproduces the order used in JPEG coefficient scanning.

Pick Zigzag diagonals and watch the direction flip.

Java
1for (int d = 0; d < R + C - 1; d++) {
2    List<int[]> cells = new ArrayList<>();
3    for (int r = Math.max(0, d - C + 1); r <= Math.min(d, R - 1); r++) cells.add(new int[]{r, d - r});
4    if (d % 2 == 0) Collections.reverse(cells);       // alternate the direction
5    for (int[] cell : cells) visit(g[cell[0]][cell[1]]);
6}

Matrix traversal orders

Interactive · edit the input

Your input

Try

grid · 3 × 4

0123
0
1
2
3
4
1
5
6
7
8
2
9
10
11
12
Visiting nowAlready visited

visit order

none yet
Setup

Spiral: walk the outer ring clockwise, then repeat on the shrinking inner matrix.

Step 1 / 14
Java
1// row-major: consecutive memory, cache friendly
2for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) visit(g[r][c]);
3// column-major: jumps a whole row each step
4for (int c = 0; c < C; c++) for (int r = 0; r < R; r++) visit(g[r][c]);
5// snake: odd rows run right to left
6for (int r = 0; r < R; r++) for (int k = 0; k < C; k++) visit(g[r][r % 2 == 0 ? k : C - 1 - k]);
7// spiral: peel the outer ring, then shrink the bounds
8int top = 0, bottom = R - 1, left = 0, right = C - 1;
9while (top <= bottom && left <= right) {
10    for (int c = left; c <= right; c++) visit(g[top][c]);                       // top side
11    for (int r = top + 1; r <= bottom; r++) visit(g[r][right]);                 // right side
12    if (top < bottom) for (int c = right - 1; c >= left; c--) visit(g[bottom][c]);   // bottom side
13    if (left < right) for (int r = bottom - 1; r > top; r--) visit(g[r][left]);      // left side
14    top++; bottom--; left++; right--;                                           // boundary-only stops after one ring
15}
16// cells with the same r + c form an anti-diagonal; zigzag reverses every other one
17for (int d = 0; d < R + C - 1; d++) {
18    for (int r = Math.max(0, d - C + 1); r <= Math.min(d, R - 1); r++) visit(g[r][d - r]);
19}

Live state

R

3

C

4

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L10R=3 C=4Spiral: walk the outer ring clockwise, then repeat on the shrinking inner matrix.
2L10step=1 r=0 c=0 g[r][c]=1Visit g[0][0] = 1 (cell 1 of 12).
3L10step=2 r=0 c=1 g[r][c]=2Visit g[0][1] = 2 (cell 2 of 12).
4L10step=3 r=0 c=2 g[r][c]=3Visit g[0][2] = 3 (cell 3 of 12).
5L10step=4 r=0 c=3 g[r][c]=4Visit g[0][3] = 4 (cell 4 of 12).
6L10step=5 r=1 c=3 g[r][c]=8Visit g[1][3] = 8 (cell 5 of 12).
7L10step=6 r=2 c=3 g[r][c]=12Visit g[2][3] = 12 (cell 6 of 12).
8L10step=7 r=2 c=2 g[r][c]=11Visit g[2][2] = 11 (cell 7 of 12).
9L10step=8 r=2 c=1 g[r][c]=10Visit g[2][1] = 10 (cell 8 of 12).
10L10step=9 r=2 c=0 g[r][c]=9Visit g[2][0] = 9 (cell 9 of 12).
11L10step=10 r=1 c=0 g[r][c]=5Visit g[1][0] = 5 (cell 10 of 12).
12L10step=11 r=1 c=1 g[r][c]=6Visit g[1][1] = 6 (cell 11 of 12).
13L10step=12 r=1 c=2 g[r][c]=7Visit g[1][2] = 7 (cell 12 of 12).
14L10return=[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]12 cells visited: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]. O(R x C) time.
10.03.4

Boundary traversal

Boundary traversal visits only the outer ring, clockwise: it is the first iteration of the spiral. A matrix with R rows and C columns (both at least 2) has 2(R + C) - 4 boundary cells. Handle R = 1 or C = 1 separately, where every cell is a boundary cell.

Choose Boundary only in the animation.

Java
1static List<Integer> boundary(int[][] g) {
2    int R = g.length, C = g[0].length;
3    List<Integer> out = new ArrayList<>();
4    for (int c = 0; c < C; c++) out.add(g[0][c]);                          // top
5    for (int r = 1; r < R; r++) out.add(g[r][C - 1]);                      // right
6    if (R > 1) for (int c = C - 2; c >= 0; c--) out.add(g[R - 1][c]);      // bottom
7    if (C > 1) for (int r = R - 2; r >= 1; r--) out.add(g[r][0]);          // left
8    return out;
9}

Matrix traversal orders

Interactive · edit the input

Your input

Try

grid · 3 × 4

0123
0
1
2
3
4
1
5
6
7
8
2
9
10
11
12
Visiting nowAlready visited

visit order

none yet
Setup

Spiral: walk the outer ring clockwise, then repeat on the shrinking inner matrix.

Step 1 / 14
Java
1// row-major: consecutive memory, cache friendly
2for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) visit(g[r][c]);
3// column-major: jumps a whole row each step
4for (int c = 0; c < C; c++) for (int r = 0; r < R; r++) visit(g[r][c]);
5// snake: odd rows run right to left
6for (int r = 0; r < R; r++) for (int k = 0; k < C; k++) visit(g[r][r % 2 == 0 ? k : C - 1 - k]);
7// spiral: peel the outer ring, then shrink the bounds
8int top = 0, bottom = R - 1, left = 0, right = C - 1;
9while (top <= bottom && left <= right) {
10    for (int c = left; c <= right; c++) visit(g[top][c]);                       // top side
11    for (int r = top + 1; r <= bottom; r++) visit(g[r][right]);                 // right side
12    if (top < bottom) for (int c = right - 1; c >= left; c--) visit(g[bottom][c]);   // bottom side
13    if (left < right) for (int r = bottom - 1; r > top; r--) visit(g[r][left]);      // left side
14    top++; bottom--; left++; right--;                                           // boundary-only stops after one ring
15}
16// cells with the same r + c form an anti-diagonal; zigzag reverses every other one
17for (int d = 0; d < R + C - 1; d++) {
18    for (int r = Math.max(0, d - C + 1); r <= Math.min(d, R - 1); r++) visit(g[r][d - r]);
19}

Live state

R

3

C

4

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L10R=3 C=4Spiral: walk the outer ring clockwise, then repeat on the shrinking inner matrix.
2L10step=1 r=0 c=0 g[r][c]=1Visit g[0][0] = 1 (cell 1 of 12).
3L10step=2 r=0 c=1 g[r][c]=2Visit g[0][1] = 2 (cell 2 of 12).
4L10step=3 r=0 c=2 g[r][c]=3Visit g[0][2] = 3 (cell 3 of 12).
5L10step=4 r=0 c=3 g[r][c]=4Visit g[0][3] = 4 (cell 4 of 12).
6L10step=5 r=1 c=3 g[r][c]=8Visit g[1][3] = 8 (cell 5 of 12).
7L10step=6 r=2 c=3 g[r][c]=12Visit g[2][3] = 12 (cell 6 of 12).
8L10step=7 r=2 c=2 g[r][c]=11Visit g[2][2] = 11 (cell 7 of 12).
9L10step=8 r=2 c=1 g[r][c]=10Visit g[2][1] = 10 (cell 8 of 12).
10L10step=9 r=2 c=0 g[r][c]=9Visit g[2][0] = 9 (cell 9 of 12).
11L10step=10 r=1 c=0 g[r][c]=5Visit g[1][0] = 5 (cell 10 of 12).
12L10step=11 r=1 c=1 g[r][c]=6Visit g[1][1] = 6 (cell 11 of 12).
13L10step=12 r=1 c=2 g[r][c]=7Visit g[1][2] = 7 (cell 12 of 12).
14L10return=[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]12 cells visited: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]. O(R x C) time.
10.03.5

Snake pattern

Snake (boustrophedon) order reads row 0 left to right, row 1 right to left, row 2 left to right, and so on, like an ox ploughing a field. It is a row traversal where odd rows are reversed, which also keeps consecutive cells adjacent. The column for step k in row r is r % 2 == 0 ? k : C - 1 - k.

Run the Snake preset.

Java
1for (int r = 0; r < R; r++)
2    for (int k = 0; k < C; k++) {
3        int c = (r % 2 == 0) ? k : C - 1 - k;
4        visit(g[r][c]);
5    }

Matrix traversal orders

Interactive · edit the input

Your input

Try

grid · 3 × 4

0123
0
1
2
3
4
1
5
6
7
8
2
9
10
11
12
Visiting nowAlready visited

visit order

none yet
Setup

Spiral: walk the outer ring clockwise, then repeat on the shrinking inner matrix.

Step 1 / 14
Java
1// row-major: consecutive memory, cache friendly
2for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) visit(g[r][c]);
3// column-major: jumps a whole row each step
4for (int c = 0; c < C; c++) for (int r = 0; r < R; r++) visit(g[r][c]);
5// snake: odd rows run right to left
6for (int r = 0; r < R; r++) for (int k = 0; k < C; k++) visit(g[r][r % 2 == 0 ? k : C - 1 - k]);
7// spiral: peel the outer ring, then shrink the bounds
8int top = 0, bottom = R - 1, left = 0, right = C - 1;
9while (top <= bottom && left <= right) {
10    for (int c = left; c <= right; c++) visit(g[top][c]);                       // top side
11    for (int r = top + 1; r <= bottom; r++) visit(g[r][right]);                 // right side
12    if (top < bottom) for (int c = right - 1; c >= left; c--) visit(g[bottom][c]);   // bottom side
13    if (left < right) for (int r = bottom - 1; r > top; r--) visit(g[r][left]);      // left side
14    top++; bottom--; left++; right--;                                           // boundary-only stops after one ring
15}
16// cells with the same r + c form an anti-diagonal; zigzag reverses every other one
17for (int d = 0; d < R + C - 1; d++) {
18    for (int r = Math.max(0, d - C + 1); r <= Math.min(d, R - 1); r++) visit(g[r][d - r]);
19}

Live state

R

3

C

4

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L10R=3 C=4Spiral: walk the outer ring clockwise, then repeat on the shrinking inner matrix.
2L10step=1 r=0 c=0 g[r][c]=1Visit g[0][0] = 1 (cell 1 of 12).
3L10step=2 r=0 c=1 g[r][c]=2Visit g[0][1] = 2 (cell 2 of 12).
4L10step=3 r=0 c=2 g[r][c]=3Visit g[0][2] = 3 (cell 3 of 12).
5L10step=4 r=0 c=3 g[r][c]=4Visit g[0][3] = 4 (cell 4 of 12).
6L10step=5 r=1 c=3 g[r][c]=8Visit g[1][3] = 8 (cell 5 of 12).
7L10step=6 r=2 c=3 g[r][c]=12Visit g[2][3] = 12 (cell 6 of 12).
8L10step=7 r=2 c=2 g[r][c]=11Visit g[2][2] = 11 (cell 7 of 12).
9L10step=8 r=2 c=1 g[r][c]=10Visit g[2][1] = 10 (cell 8 of 12).
10L10step=9 r=2 c=0 g[r][c]=9Visit g[2][0] = 9 (cell 9 of 12).
11L10step=10 r=1 c=0 g[r][c]=5Visit g[1][0] = 5 (cell 10 of 12).
12L10step=11 r=1 c=1 g[r][c]=6Visit g[1][1] = 6 (cell 11 of 12).
13L10step=12 r=1 c=2 g[r][c]=7Visit g[1][2] = 7 (cell 12 of 12).
14L10return=[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]12 cells visited: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]. O(R x C) time.

Practice ladder

Now try it yourself

Easy

  • Write the spiral order of [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
  • How many boundary cells does a 5 × 7 matrix have?

Medium

  • List the anti-diagonals of a 3 × 4 matrix
  • Why is the guard top < bottom needed in the spiral loop?

Advanced

  • Fill an n × n matrix with 1..n² in spiral order

Key takeaways

  • Spiral uses four shrinking bounds and two guards for the last row or column.
  • Anti-diagonals are the cells with equal r + c; zigzag alternates their direction.
  • Boundary traversal has 2(R + C) - 4 cells when R, C ≥ 2.