Data Structures & AlgorithmsMulti-Dimensional Arrays

Multi-Dimensional Arrays — Extending Arrays to Grids and Beyond

LevelBeginner

Duration60 mins

TopicMulti-Dimensional Arrays

3 / 4

Traversing Matrices — Row-wise, Column-wise, Diagonal

The Art of Walking Through Grids

Almost every operation on a matrix—summing elements, finding maximums, transforming values, detecting patterns—requires systematically visiting elements. But unlike a 1D array where you simply go from start to end, a 2D array offers multiple ways to traverse.

The traversal pattern you choose isn't arbitrary. Different problems demand different patterns: finding row sums requires row-wise traversal, checking diagonals for a game of tic-tac-toe requires diagonal traversal, and image processing filters might need to visit neighbors in specific orders.

Mastering these traversal patterns is like learning the basic strokes in painting—once internalized, you can combine them to create sophisticated algorithms.

What You Will Learn

By the end of this page, you will be able to traverse matrices row-wise, column-wise, diagonally (both directions), and in spiral order. You'll understand when each pattern is appropriate, how to implement them correctly with proper bounds checking, and how to recognize which traversal a problem requires.

Row-wise Traversal: The Natural Order

Row-wise traversal is the most intuitive pattern: visit all elements in row 0 from left to right, then all elements in row 1, and so on. This matches how we read text (in left-to-right languages) and how row-major storage works.

The Pattern:

row-wise-traversal.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]
 
// Basic row-wise traversal
for row in range(len(matrix)):           // 0, 1, 2
    for col in range(len(matrix[0])):    // 0, 1, 2, 3
        print(matrix[row][col], end=" ")
    print()  // Newline after each row
 
// Output:
// 1 2 3 4
// 5 6 7 8
// 9 10 11 12
 
// Visit order: [0][0] → [0][1] → [0][2] → [0][3] → [1][0] → ... → [2][3]

Common Use Cases:

•Sum/average of all elements — Visit every element exactly once, accumulating values
•Finding minimum/maximum — Track extreme values across all elements
•Transforming each element — Apply a function to every cell (e.g., incrementing, squaring)
•Printing/displaying the matrix — Output in human-readable format
•Counting occurrences — How many times does value X appear?
•Flattening to 1D — As covered previously, this produces the row-major flat array

Processing Individual Rows:

Often you need to compute something for each row separately:

row-processing.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
matrix = [
    [85, 90, 78],   // Alice's grades
    [92, 88, 95],   // Bob's grades
    [76, 82, 80]    // Charlie's grades
]
 
// Calculate average grade per student
for row in range(len(matrix)):
    row_sum = 0
    for col in range(len(matrix[0])):
        row_sum += matrix[row][col]
    average = row_sum / len(matrix[0])
    print(f"Student {row}: Average = {average:.1f}")
 
// Output:
// Student 0: Average = 84.3
// Student 1: Average = 91.7
// Student 2: Average = 79.3
 
// Alternative: work with each row as a sub-array
for row_idx, row in enumerate(matrix):
    print(f"Student {row_idx}: Average = {sum(row) / len(row):.1f}")

Performance Note

Row-wise traversal is cache-optimal for row-major storage (C, Python, Java). Elements in the same row are adjacent in memory, so this pattern maximizes cache hits. Always prefer row-wise unless your problem specifically requires a different order.

Column-wise Traversal: The Vertical View

Column-wise traversal visits all elements in column 0 from top to bottom, then all elements in column 1, and so on. This is essential when your problem naturally organizes data by columns.

The Pattern:

column-wise-traversal.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]
 
rows = len(matrix)         // 3
cols = len(matrix[0])      // 4
 
// Column-wise traversal: outer loop on columns
for col in range(cols):            // 0, 1, 2, 3
    for row in range(rows):        // 0, 1, 2
        print(matrix[row][col], end=" ")
    print()  // Newline after each column
 
// Output:
// 1 5 9
// 2 6 10
// 3 7 11
// 4 8 12
 
// Visit order: [0][0] → [1][0] → [2][0] → [0][1] → [1][1] → ... → [2][3]

Common Use Cases:

•Column sums/averages — Calculate statistics for each column (e.g., average score per assignment)
•Finding column min/max — Identify extreme values per column
•Transposing a matrix — Swap rows and columns
•Checking column conditions — Does this column satisfy a property?
•Matrix operations in column-major libraries — Aligns with Fortran/MATLAB conventions

Processing Individual Columns:

Unlike rows, columns aren't contiguous in memory for row-major arrays, so accessing a full column requires extracting elements:

column-processing.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
matrix = [
    [85, 90, 78],   // Grades: Assignment 1, 2, 3
    [92, 88, 95],   // Grades: Assignment 1, 2, 3
    [76, 82, 80]    // Grades: Assignment 1, 2, 3
]
 
rows = len(matrix)
cols = len(matrix[0])
 
// Calculate average grade per assignment
for col in range(cols):
    col_sum = 0
    for row in range(rows):
        col_sum += matrix[row][col]
    average = col_sum / rows
    print(f"Assignment {col + 1}: Class average = {average:.1f}")
 
// Output:
// Assignment 1: Class average = 84.3
// Assignment 2: Class average = 86.7
// Assignment 3: Class average = 84.3
 
// Extracting a column as a list
def get_column(matrix, col_index):
    return [matrix[row][col_index] for row in range(len(matrix))]
 
assignment_1_grades = get_column(matrix, 0)  // [85, 92, 76]

Performance Consideration

Column-wise traversal in row-major languages causes cache misses because each access jumps to a different cache line. For large matrices where performance matters, consider transposing the matrix first if you need many column-wise operations, then work row-wise on the transposed data.

Diagonal Traversal: Main Diagonal

The main diagonal (also called the principal diagonal) runs from the top-left corner to the bottom-right corner. Elements on the main diagonal have equal row and column indices: matrix[0][0], matrix[1][1], matrix[2][2], etc.

Traversing the Main Diagonal:

main-diagonal.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]
 
// The main diagonal exists only where row index = column index
// For a 3×4 matrix, main diagonal elements: [0][0], [1][1], [2][2]
// (We can't have [3][3] because there are only 3 rows)
 
rows = len(matrix)      // 3
cols = len(matrix[0])   // 4
diagonal_length = min(rows, cols)  // 3
 
// Traverse main diagonal
print("Main diagonal:", end=" ")
for i in range(diagonal_length):
    print(matrix[i][i], end=" ")
// Output: Main diagonal: 1 6 11
 
// Sum of main diagonal (trace of a matrix)
trace = sum(matrix[i][i] for i in range(diagonal_length))
print(f"Trace = {trace}")  // Trace = 18

Visualizing the Main Diagonal:

main-diagonal-visual.txt
Matrix (3×4):
     Col 0   Col 1   Col 2   Col 3
     ┌───────┬───────┬───────┬───────┐
Row 0│ [1]◄──│   2   │   3   │   4   │  Main diagonal element
     ├───────┼───────┼───────┼───────┤
Row 1│   5   │ [6]◄──│   7   │   8   │  Main diagonal element
     ├───────┼───────┼───────┼───────┤
Row 2│   9   │  10   │[11]◄──│  12   │  Main diagonal element
     └───────┴───────┴───────┴───────┘
                              ↑
                     [3][3] doesn't exist (only 3 rows)
 
Key insight: On the main diagonal, row index equals column index.

Common Use Cases:

•Computing the trace — Sum of main diagonal elements in square matrices (important in linear algebra)
•Identity matrix verification — Check if 1s are on diagonal, 0s elsewhere
•Tic-tac-toe/diagonal games — Check for winning lines
•Diagonal dominance — Verify matrix properties for numerical stability
•Matrix initialization — Set diagonal elements (e.g., identity matrix)

Square vs Rectangular Matrices

For square matrices (n×n), the main diagonal has exactly n elements. For rectangular matrices (m×n), the main diagonal has min(m, n) elements—it ends when either row or column indices run out.

Diagonal Traversal: Anti-Diagonal

The anti-diagonal (also called secondary diagonal or back diagonal) runs from the top-right corner to the bottom-left corner. Elements on the anti-diagonal satisfy the property: row + col = n - 1 for an n×n matrix, or more generally row + col = constant.

Traversing the Anti-Diagonal:

anti-diagonal.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]
 
// For a 3×4 matrix, we can traverse the anti-diagonal where row + col = constant
// The main anti-diagonal (top-right to bottom-left of the valid region):
// When rows = 3, cols = 4, we look at row + col = min(rows, cols) - 1 = 2
// Elements: [0][2], [1][1], [2][0]
 
rows = len(matrix)      // 3
cols = len(matrix[0])   // 4
anti_diag_length = min(rows, cols)
 
// Traverse shortest anti-diagonal (from position [0][rows-1])
print("Anti-diagonal:", end=" ")
for i in range(anti_diag_length):
    row = i
    col = (anti_diag_length - 1) - i  // Start from rightmost column
    print(matrix[row][col], end=" ")
// Output: Anti-diagonal: 3 6 9
 
// For a square matrix, the main anti-diagonal is simpler:
// Elements [i][n-1-i] for i in 0 to n-1

Visualizing the Anti-Diagonal:

anti-diagonal-visual.txt
Matrix (3×4):
     Col 0   Col 1   Col 2   Col 3
     ┌───────┬───────┬───────┬───────┐
Row 0│   1   │   2   │ [3]◄──│   4   │  Anti-diagonal: row + col = 2
     ├───────┼───────┼───────┼───────┤
Row 1│   5   │ [6]◄──│   7   │   8   │  Anti-diagonal: row + col = 2
     ├───────┼───────┼───────┼───────┤
Row 2│ [9]◄──│  10   │  11   │  12   │  Anti-diagonal: row + col = 2
     └───────┴───────┴───────┴───────┘
 
Key insight: On an anti-diagonal, row + col is constant.
 
For a 4×4 square matrix, the main anti-diagonal:
     ┌───────┬───────┬───────┬───────┐
     │       │       │       │ [0,3] │  row + col = 3
     ├───────┼───────┼───────┼───────┤
     │       │       │ [1,2] │       │  row + col = 3
     ├───────┼───────┼───────┼───────┤
     │       │ [2,1] │       │       │  row + col = 3
     ├───────┼───────┼───────┼───────┤
     │ [3,0] │       │       │       │  row + col = 3
     └───────┴───────┴───────┴───────┘

Traversing All Diagonals:

Many problems require visiting all diagonals (not just the main one). Each diagonal is characterized by a constant row + col value:

all-anti-diagonals.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
matrix = [
    [1,  2,  3],
    [4,  5,  6],
    [7,  8,  9]
]
 
rows, cols = 3, 3
 
// There are (rows + cols - 1) anti-diagonals
// For 3×3: diagonals with sum = 0, 1, 2, 3, 4
num_diagonals = rows + cols - 1  // 5
 
for diag_sum in range(num_diagonals):  // 0 to 4
    print(f"Diagonal (sum={diag_sum}):", end=" ")
    // Row ranges from max(0, diag_sum - cols + 1) to min(rows - 1, diag_sum)
    row_start = max(0, diag_sum - cols + 1)
    row_end = min(rows - 1, diag_sum)
    for row in range(row_start, row_end + 1):
        col = diag_sum - row
        print(f"[{row}][{col}]={matrix[row][col]}", end=" ")
    print()
 
// Output:
// Diagonal (sum=0): [0][0]=1
// Diagonal (sum=1): [0][1]=2 [1][0]=4
// Diagonal (sum=2): [0][2]=3 [1][1]=5 [2][0]=7
// Diagonal (sum=3): [1][2]=6 [2][1]=8
// Diagonal (sum=4): [2][2]=9

Diagonal Problem Pattern

When a problem involves diagonals, the key insight is that elements on the same anti-diagonal share a constant (row + col) value. You can use this sum as a hash key to group elements by diagonal.

Traversing All Diagonals (Both Directions)

Sometimes you need to work with diagonals in both directions: the main diagonal direction (↘) and the anti-diagonal direction (↙). Here's how to systematically traverse all diagonals in both directions.

Main Diagonal Direction () — All Parallel Diagonals:

all-main-direction-diagonals.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]
 
rows, cols = 3, 4
 
// Diagonals parallel to main diagonal: characterized by (row - col) = constant
// Possible values range from -(cols-1) to (rows-1)
// For 3×4: constants are -3, -2, -1, 0, 1, 2
 
// Easier approach: start from each cell in first row and first column
# Visit diagonals starting from top edge (row 0)
for start_col in range(cols):  // 0, 1, 2, 3
    row, col = 0, start_col
    print(f"Diagonal from [0][{start_col}]:", end=" ")
    while row < rows and col < cols:
        print(matrix[row][col], end=" ")
        row += 1
        col += 1
    print()
 
# Visit diagonals starting from left edge (col 0), except [0][0] already done
for start_row in range(1, rows):  // 1, 2
    row, col = start_row, 0
    print(f"Diagonal from [{start_row}][0]:", end=" ")
    while row < rows and col < cols:
        print(matrix[row][col], end=" ")
        row += 1
        col += 1
    print()
 
// Output:
// Diagonal from [0][0]: 1 6 11
// Diagonal from [0][1]: 2 7 12
// Diagonal from [0][2]: 3 8
// Diagonal from [0][3]: 4
// Diagonal from [1][0]: 5 10
// Diagonal from [2][0]: 9

Anti-Diagonal Direction (/) — All Parallel Diagonals:

all-anti-direction-diagonals.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]
 
rows, cols = 3, 4
 
# Visit diagonals starting from top edge (row 0), going ↙
for start_col in range(cols):  // 0, 1, 2, 3
    row, col = 0, start_col
    print(f"Anti-diagonal from [0][{start_col}]:", end=" ")
    while row < rows and col >= 0:
        print(matrix[row][col], end=" ")
        row += 1
        col -= 1  // Moving left
    print()
 
# Visit diagonals starting from right edge (col = cols-1), except [0][cols-1] already done
for start_row in range(1, rows):  // 1, 2
    row, col = start_row, cols - 1
    print(f"Anti-diagonal from [{start_row}][{cols-1}]:", end=" ")
    while row < rows and col >= 0:
        print(matrix[row][col], end=" ")
        row += 1
        col -= 1
    print()
 
// Output:
// Anti-diagonal from [0][0]: 1
// Anti-diagonal from [0][1]: 2 5
// Anti-diagonal from [0][2]: 3 6 9
// Anti-diagonal from [0][3]: 4 7 10
// Anti-diagonal from [1][3]: 8 11
// Anti-diagonal from [2][3]: 12

Diagonal Characterization

For main-direction diagonals (↘), elements share the same (row - col) value. For anti-diagonals (↙), elements share the same (row + col) value. These constants can serve as keys to group or identify diagonals.

Spiral Traversal: The Classic Pattern

Spiral traversal visits elements starting from the outer boundary, moving inward in a spiral pattern. This is a classic interview problem that tests boundary management skills.

The Pattern:

Start at top-left, move right along the top edge, down the right edge, left along the bottom edge, up the left edge, then repeat for the inner rectangle.

spiral-traversal-visual.txt
Matrix (3×4):
     ┌───────┬───────┬───────┬───────┐
     │  1  →│  2  →│  3  →│  4  │   Layer 1: top row (left to right)
     ├───────┼───────┼───────┼──│────┤
     │  5   │  6  →│  7   │  8↓ │   Layer 2 starts at 6,7 (inner)
     ├───────┼───────┼───────┼──│────┤
     │ ←10  │ ←11  │ ←12  │  9  │   Layer 1: bottom row (right to left)
     └───────┴───────┴───────┴───────┘
       ↑
     Layer 1: left column (bottom to top, but only element 5 remains)
 
Spiral order: 1 → 2 → 3 → 4 → 8 → 12 → 11 → 10 → 9 → 5 → 6 → 7
 
For a 3×4 matrix, after the outer layer, what remains is just [6, 7]

spiral-traversal.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def spiral_traversal(matrix):
    if not matrix or not matrix[0]:
        return []
    
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    
    while top <= bottom and left <= right:
        // 1. Traverse top row (left to right)
        for col in range(left, right + 1):
            result.append(matrix[top][col])
        top += 1  // Shrink top boundary
        
        // 2. Traverse right column (top to bottom)
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1  // Shrink right boundary
        
        // 3. Traverse bottom row (right to left) - if rows remain
        if top <= bottom:
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1  // Shrink bottom boundary
        
        // 4. Traverse left column (bottom to top) - if columns remain
        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1  // Shrink left boundary
    
    return result
 
// Example:
matrix = [[1,2,3,4], [5,6,7,8], [9,10,11,12]]
print(spiral_traversal(matrix))
// Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Boundary Conditions

The checks if top <= bottom and if left <= right are critical. Without them, you'll traverse elements twice for matrices with odd dimensions. For example, a single row remaining after outer layers would be traversed twice (once going right, once going left) without these guards.

Common Use Cases:

•Spiral print/flatten — Classic interview problem
•Image processing — Spiral blur or effect application
•Game mechanics — Spiral reveal of a game board
•Generating spiral matrices — Fill a matrix in spiral order

Boundary Traversal and Wave Patterns

Beyond spirals, there are other specialized traversal patterns worth knowing.

Boundary (Perimeter) Traversal:

Visit only the outer edge of the matrix:

boundary-traversal.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def boundary_traversal(matrix):
    if not matrix or not matrix[0]:
        return []
    
    rows, cols = len(matrix), len(matrix[0])
    result = []
    
    // Handle edge cases
    if rows == 1:
        return matrix[0][:]  // Single row
    if cols == 1:
        return [matrix[i][0] for i in range(rows)]  // Single column
    
    // Top row (all elements)
    for col in range(cols):
        result.append(matrix[0][col])
    
    // Right column (excluding top corner)
    for row in range(1, rows):
        result.append(matrix[row][cols-1])
    
    // Bottom row (excluding right corner, reversed)
    for col in range(cols-2, -1, -1):
        result.append(matrix[rows-1][col])
    
    // Left column (excluding both corners, reversed)
    for row in range(rows-2, 0, -1):
        result.append(matrix[row][0])
    
    return result
 
matrix = [[1,2,3], [4,5,6], [7,8,9]]
print(boundary_traversal(matrix))
// Output: [1, 2, 3, 6, 9, 8, 7, 4]  (excludes center 5)

Zigzag (Wave) Traversal:

Alternate direction on each row—go right on even rows, left on odd rows:

zigzag-traversal.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]
 
result = []
rows, cols = len(matrix), len(matrix[0])
 
for row in range(rows):
    if row % 2 == 0:
        // Even row: left to right
        for col in range(cols):
            result.append(matrix[row][col])
    else:
        // Odd row: right to left
        for col in range(cols - 1, -1, -1):
            result.append(matrix[row][col])
 
print(result)
// Output: [1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11, 12]
 
// Visual:
// Row 0: 1 → 2 → 3 → 4
// Row 1: 8 ← 7 ← 6 ← 5
// Row 2: 9 → 10 → 11 → 12

Diagonal Zigzag (Used in JPEG compression):

This pattern visits elements along successive diagonals, alternating direction:

diagonal-zigzag.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
// JPEG zigzag pattern for 8×8 block (simplified for 3×3)
matrix = [
    [0, 1, 5],
    [2, 4, 6],
    [3, 7, 8]
]
 
// Numbers show the visit order in zigzag:
// [0,0] → [0,1] → [1,0] → [2,0] → [1,1] → [0,2] → [1,2] → [2,1] → [2,2]
// Values: 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
 
// This is used because early diagonal values (low frequencies)
// are more important in image compression

Pattern Recognition

Each traversal pattern has specific use cases. Row-wise for general processing, column-wise for vertical aggregations, diagonals for checking winning conditions or certain mathematical properties, spiral for layer-by-layer processing, and zigzag for reducing direction changes (useful in physical devices like printers or in compression algorithms).

Neighbor Traversal: 4-Direction and 8-Direction

Many matrix algorithms need to access the neighbors of a cell. Understanding how to correctly enumerate neighbors is crucial for flood fill, pathfinding, image filters, and cellular automata.

4-Directional Neighbors (Cardinal Directions):

four-direction-neighbors.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 4-directional: up, down, left, right
// Direction vectors: (row_delta, col_delta)
DIRECTIONS_4 = [
    (-1, 0),  // Up
    (1, 0),   // Down
    (0, -1),  // Left
    (0, 1)    // Right
]
 
def get_4_neighbors(matrix, row, col):
    rows, cols = len(matrix), len(matrix[0])
    neighbors = []
    
    for dr, dc in DIRECTIONS_4:
        new_row, new_col = row + dr, col + dc
        // Check bounds
        if 0 <= new_row < rows and 0 <= new_col < cols:
            neighbors.append((new_row, new_col))
    
    return neighbors
 
// Example: neighbors of [1][1] in a 3×3 matrix
matrix = [[1,2,3], [4,5,6], [7,8,9]]
print(get_4_neighbors(matrix, 1, 1))
// Output: [(0,1), (2,1), (1,0), (1,2)] → cells with values 2, 8, 4, 6
 
// Corner case: neighbors of [0][0]
print(get_4_neighbors(matrix, 0, 0))
// Output: [(1,0), (0,1)] → only 2 neighbors (Down, Right)

8-Directional Neighbors (Including Diagonals):

eight-direction-neighbors.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 8-directional: includes diagonal neighbors
DIRECTIONS_8 = [
    (-1, 0),   // Up
    (1, 0),    // Down
    (0, -1),   // Left
    (0, 1),    // Right
    (-1, -1),  // Up-Left (diagonal)
    (-1, 1),   // Up-Right (diagonal)
    (1, -1),   // Down-Left (diagonal)
    (1, 1)     // Down-Right (diagonal)
]
 
def get_8_neighbors(matrix, row, col):
    rows, cols = len(matrix), len(matrix[0])
    neighbors = []
    
    for dr, dc in DIRECTIONS_8:
        new_row, new_col = row + dr, col + dc
        if 0 <= new_row < rows and 0 <= new_col < cols:
            neighbors.append((new_row, new_col))
    
    return neighbors
 
// Example: neighbors of [1][1] in a 3×3 matrix
matrix = [[1,2,3], [4,5,6], [7,8,9]]
print(get_8_neighbors(matrix, 1, 1))
// Output: All 8 surrounding cells (the center 5 is surrounded by 1-4, 6-9)
 
// Visualization:
//  [0,0] [0,1] [0,2]     1 2 3     ↖ ↑ ↗
//  [1,0] [1,1] [1,2]  =  4 5 6  =  ← ● →
//  [2,0] [2,1] [2,2]     7 8 9     ↙ ↓ ↘

Common Use Cases:

When to Use Each Neighbor Pattern
Pattern	Count	Use Cases
4-directional	Up to 4	Maze navigation, flood fill, BFS shortest path on grids
8-directional	Up to 8	Game of Life, image blur, unrestricted grid movement
Knight moves	Up to 8	Chess knight, specific jump patterns
Custom	Varies	Domain-specific movement rules

Always Check Bounds

The most common bug in neighbor traversal is forgetting to check if the new position is within matrix bounds. Cells on edges and corners have fewer neighbors than interior cells. Always validate with: 0 <= new_row < rows and 0 <= new_col < cols.

Summary: Traversal Pattern Mastery

Key Takeaways

•Row-wise traversal — Outer loop on rows, inner on columns. Cache-optimal for row-major storage. Use for general element processing.
•Column-wise traversal — Outer loop on columns, inner on rows. Use for column-specific operations. Beware of cache inefficiency in row-major languages.
•Main diagonal — Elements where row == col. Use for trace, identity checks, diagonal games.
•Anti-diagonal — Elements where row + col is constant. Use for opposite diagonal checks and grouping.
•All diagonals — For main direction: row - col is constant. For anti-direction: row + col is constant.
•Spiral traversal — Layer-by-layer from outside in. Manage four boundaries carefully.
•Boundary traversal — Only the perimeter elements.
•Zigzag traversal — Alternating direction per row/diagonal.
•Neighbor traversal — 4-directional for cardinal directions, 8-directional including diagonals. Always validate bounds.

What's Next:

Now that you can traverse matrices in any pattern, we'll explore the common matrix operations and patterns that build on these traversals. You'll learn about matrix rotation, transposition, searching in sorted matrices, and other essential operations that appear throughout algorithm problems.

Page Complete

You've mastered the fundamental traversal patterns for matrices. These patterns are the building blocks of virtually every matrix algorithm. Whether you're processing images, solving grid puzzles, or implementing graph algorithms on implicit grids, you now have the tools to systematically visit elements in any order your problem requires.

3 / 4

Loading learning content...

Data Structures & AlgorithmsMulti-Dimensional Arrays

Multi-Dimensional Arrays — Extending Arrays to Grids and Beyond

LevelBeginner

Duration60 mins

TopicMulti-Dimensional Arrays

3 / 4

Traversing Matrices — Row-wise, Column-wise, Diagonal

The Art of Walking Through Grids

Mastering these traversal patterns is like learning the basic strokes in painting—once internalized, you can combine them to create sophisticated algorithms.

What You Will Learn

Row-wise Traversal: The Natural Order

The Pattern:

row-wise-traversal.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]
 
// Basic row-wise traversal
for row in range(len(matrix)):           // 0, 1, 2
    for col in range(len(matrix[0])):    // 0, 1, 2, 3
        print(matrix[row][col], end=" ")
    print()  // Newline after each row
 
// Output:
// 1 2 3 4
// 5 6 7 8
// 9 10 11 12
 
// Visit order: [0][0] → [0][1] → [0][2] → [0][3] → [1][0] → ... → [2][3]

Common Use Cases:

•Sum/average of all elements — Visit every element exactly once, accumulating values
•Finding minimum/maximum — Track extreme values across all elements
•Transforming each element — Apply a function to every cell (e.g., incrementing, squaring)
•Printing/displaying the matrix — Output in human-readable format
•Counting occurrences — How many times does value X appear?
•Flattening to 1D — As covered previously, this produces the row-major flat array

Processing Individual Rows:

Often you need to compute something for each row separately:

row-processing.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
matrix = [
    [85, 90, 78],   // Alice's grades
    [92, 88, 95],   // Bob's grades
    [76, 82, 80]    // Charlie's grades
]
 
// Calculate average grade per student
for row in range(len(matrix)):
    row_sum = 0
    for col in range(len(matrix[0])):
        row_sum += matrix[row][col]
    average = row_sum / len(matrix[0])
    print(f"Student {row}: Average = {average:.1f}")
 
// Output:
// Student 0: Average = 84.3
// Student 1: Average = 91.7
// Student 2: Average = 79.3
 
// Alternative: work with each row as a sub-array
for row_idx, row in enumerate(matrix):
    print(f"Student {row_idx}: Average = {sum(row) / len(row):.1f}")

Performance Note

Column-wise Traversal: The Vertical View

Column-wise traversal visits all elements in column 0 from top to bottom, then all elements in column 1, and so on. This is essential when your problem naturally organizes data by columns.

The Pattern:

column-wise-traversal.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]
 
rows = len(matrix)         // 3
cols = len(matrix[0])      // 4
 
// Column-wise traversal: outer loop on columns
for col in range(cols):            // 0, 1, 2, 3
    for row in range(rows):        // 0, 1, 2
        print(matrix[row][col], end=" ")
    print()  // Newline after each column
 
// Output:
// 1 5 9
// 2 6 10
// 3 7 11
// 4 8 12
 
// Visit order: [0][0] → [1][0] → [2][0] → [0][1] → [1][1] → ... → [2][3]

Common Use Cases:

•Column sums/averages — Calculate statistics for each column (e.g., average score per assignment)
•Finding column min/max — Identify extreme values per column
•Transposing a matrix — Swap rows and columns
•Checking column conditions — Does this column satisfy a property?
•Matrix operations in column-major libraries — Aligns with Fortran/MATLAB conventions

Processing Individual Columns:

Unlike rows, columns aren't contiguous in memory for row-major arrays, so accessing a full column requires extracting elements:

column-processing.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
matrix = [
    [85, 90, 78],   // Grades: Assignment 1, 2, 3
    [92, 88, 95],   // Grades: Assignment 1, 2, 3
    [76, 82, 80]    // Grades: Assignment 1, 2, 3
]
 
rows = len(matrix)
cols = len(matrix[0])
 
// Calculate average grade per assignment
for col in range(cols):
    col_sum = 0
    for row in range(rows):
        col_sum += matrix[row][col]
    average = col_sum / rows
    print(f"Assignment {col + 1}: Class average = {average:.1f}")
 
// Output:
// Assignment 1: Class average = 84.3
// Assignment 2: Class average = 86.7
// Assignment 3: Class average = 84.3
 
// Extracting a column as a list
def get_column(matrix, col_index):
    return [matrix[row][col_index] for row in range(len(matrix))]
 
assignment_1_grades = get_column(matrix, 0)  // [85, 92, 76]

Performance Consideration

Diagonal Traversal: Main Diagonal

Traversing the Main Diagonal:

main-diagonal.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]
 
// The main diagonal exists only where row index = column index
// For a 3×4 matrix, main diagonal elements: [0][0], [1][1], [2][2]
// (We can't have [3][3] because there are only 3 rows)
 
rows = len(matrix)      // 3
cols = len(matrix[0])   // 4
diagonal_length = min(rows, cols)  // 3
 
// Traverse main diagonal
print("Main diagonal:", end=" ")
for i in range(diagonal_length):
    print(matrix[i][i], end=" ")
// Output: Main diagonal: 1 6 11
 
// Sum of main diagonal (trace of a matrix)
trace = sum(matrix[i][i] for i in range(diagonal_length))
print(f"Trace = {trace}")  // Trace = 18

Visualizing the Main Diagonal:

main-diagonal-visual.txt
Matrix (3×4):
     Col 0   Col 1   Col 2   Col 3
     ┌───────┬───────┬───────┬───────┐
Row 0│ [1]◄──│   2   │   3   │   4   │  Main diagonal element
     ├───────┼───────┼───────┼───────┤
Row 1│   5   │ [6]◄──│   7   │   8   │  Main diagonal element
     ├───────┼───────┼───────┼───────┤
Row 2│   9   │  10   │[11]◄──│  12   │  Main diagonal element
     └───────┴───────┴───────┴───────┘
                              ↑
                     [3][3] doesn't exist (only 3 rows)
 
Key insight: On the main diagonal, row index equals column index.

Common Use Cases:

•Computing the trace — Sum of main diagonal elements in square matrices (important in linear algebra)
•Identity matrix verification — Check if 1s are on diagonal, 0s elsewhere
•Tic-tac-toe/diagonal games — Check for winning lines
•Diagonal dominance — Verify matrix properties for numerical stability
•Matrix initialization — Set diagonal elements (e.g., identity matrix)

Square vs Rectangular Matrices

For square matrices (n×n), the main diagonal has exactly n elements. For rectangular matrices (m×n), the main diagonal has min(m, n) elements—it ends when either row or column indices run out.

Diagonal Traversal: Anti-Diagonal

Traversing the Anti-Diagonal:

anti-diagonal.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]
 
// For a 3×4 matrix, we can traverse the anti-diagonal where row + col = constant
// The main anti-diagonal (top-right to bottom-left of the valid region):
// When rows = 3, cols = 4, we look at row + col = min(rows, cols) - 1 = 2
// Elements: [0][2], [1][1], [2][0]
 
rows = len(matrix)      // 3
cols = len(matrix[0])   // 4
anti_diag_length = min(rows, cols)
 
// Traverse shortest anti-diagonal (from position [0][rows-1])
print("Anti-diagonal:", end=" ")
for i in range(anti_diag_length):
    row = i
    col = (anti_diag_length - 1) - i  // Start from rightmost column
    print(matrix[row][col], end=" ")
// Output: Anti-diagonal: 3 6 9
 
// For a square matrix, the main anti-diagonal is simpler:
// Elements [i][n-1-i] for i in 0 to n-1

Visualizing the Anti-Diagonal:

anti-diagonal-visual.txt
Matrix (3×4):
     Col 0   Col 1   Col 2   Col 3
     ┌───────┬───────┬───────┬───────┐
Row 0│   1   │   2   │ [3]◄──│   4   │  Anti-diagonal: row + col = 2
     ├───────┼───────┼───────┼───────┤
Row 1│   5   │ [6]◄──│   7   │   8   │  Anti-diagonal: row + col = 2
     ├───────┼───────┼───────┼───────┤
Row 2│ [9]◄──│  10   │  11   │  12   │  Anti-diagonal: row + col = 2
     └───────┴───────┴───────┴───────┘
 
Key insight: On an anti-diagonal, row + col is constant.
 
For a 4×4 square matrix, the main anti-diagonal:
     ┌───────┬───────┬───────┬───────┐
     │       │       │       │ [0,3] │  row + col = 3
     ├───────┼───────┼───────┼───────┤
     │       │       │ [1,2] │       │  row + col = 3
     ├───────┼───────┼───────┼───────┤
     │       │ [2,1] │       │       │  row + col = 3
     ├───────┼───────┼───────┼───────┤
     │ [3,0] │       │       │       │  row + col = 3
     └───────┴───────┴───────┴───────┘

Traversing All Diagonals:

Many problems require visiting all diagonals (not just the main one). Each diagonal is characterized by a constant row + col value:

all-anti-diagonals.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
matrix = [
    [1,  2,  3],
    [4,  5,  6],
    [7,  8,  9]
]
 
rows, cols = 3, 3
 
// There are (rows + cols - 1) anti-diagonals
// For 3×3: diagonals with sum = 0, 1, 2, 3, 4
num_diagonals = rows + cols - 1  // 5
 
for diag_sum in range(num_diagonals):  // 0 to 4
    print(f"Diagonal (sum={diag_sum}):", end=" ")
    // Row ranges from max(0, diag_sum - cols + 1) to min(rows - 1, diag_sum)
    row_start = max(0, diag_sum - cols + 1)
    row_end = min(rows - 1, diag_sum)
    for row in range(row_start, row_end + 1):
        col = diag_sum - row
        print(f"[{row}][{col}]={matrix[row][col]}", end=" ")
    print()
 
// Output:
// Diagonal (sum=0): [0][0]=1
// Diagonal (sum=1): [0][1]=2 [1][0]=4
// Diagonal (sum=2): [0][2]=3 [1][1]=5 [2][0]=7
// Diagonal (sum=3): [1][2]=6 [2][1]=8
// Diagonal (sum=4): [2][2]=9

Diagonal Problem Pattern

When a problem involves diagonals, the key insight is that elements on the same anti-diagonal share a constant (row + col) value. You can use this sum as a hash key to group elements by diagonal.

Traversing All Diagonals (Both Directions)

Main Diagonal Direction () — All Parallel Diagonals:

all-main-direction-diagonals.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]
 
rows, cols = 3, 4
 
// Diagonals parallel to main diagonal: characterized by (row - col) = constant
// Possible values range from -(cols-1) to (rows-1)
// For 3×4: constants are -3, -2, -1, 0, 1, 2
 
// Easier approach: start from each cell in first row and first column
# Visit diagonals starting from top edge (row 0)
for start_col in range(cols):  // 0, 1, 2, 3
    row, col = 0, start_col
    print(f"Diagonal from [0][{start_col}]:", end=" ")
    while row < rows and col < cols:
        print(matrix[row][col], end=" ")
        row += 1
        col += 1
    print()
 
# Visit diagonals starting from left edge (col 0), except [0][0] already done
for start_row in range(1, rows):  // 1, 2
    row, col = start_row, 0
    print(f"Diagonal from [{start_row}][0]:", end=" ")
    while row < rows and col < cols:
        print(matrix[row][col], end=" ")
        row += 1
        col += 1
    print()
 
// Output:
// Diagonal from [0][0]: 1 6 11
// Diagonal from [0][1]: 2 7 12
// Diagonal from [0][2]: 3 8
// Diagonal from [0][3]: 4
// Diagonal from [1][0]: 5 10
// Diagonal from [2][0]: 9

Anti-Diagonal Direction (/) — All Parallel Diagonals:

all-anti-direction-diagonals.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]
 
rows, cols = 3, 4
 
# Visit diagonals starting from top edge (row 0), going ↙
for start_col in range(cols):  // 0, 1, 2, 3
    row, col = 0, start_col
    print(f"Anti-diagonal from [0][{start_col}]:", end=" ")
    while row < rows and col >= 0:
        print(matrix[row][col], end=" ")
        row += 1
        col -= 1  // Moving left
    print()
 
# Visit diagonals starting from right edge (col = cols-1), except [0][cols-1] already done
for start_row in range(1, rows):  // 1, 2
    row, col = start_row, cols - 1
    print(f"Anti-diagonal from [{start_row}][{cols-1}]:", end=" ")
    while row < rows and col >= 0:
        print(matrix[row][col], end=" ")
        row += 1
        col -= 1
    print()
 
// Output:
// Anti-diagonal from [0][0]: 1
// Anti-diagonal from [0][1]: 2 5
// Anti-diagonal from [0][2]: 3 6 9
// Anti-diagonal from [0][3]: 4 7 10
// Anti-diagonal from [1][3]: 8 11
// Anti-diagonal from [2][3]: 12

Diagonal Characterization

Spiral Traversal: The Classic Pattern

Spiral traversal visits elements starting from the outer boundary, moving inward in a spiral pattern. This is a classic interview problem that tests boundary management skills.

The Pattern:

Start at top-left, move right along the top edge, down the right edge, left along the bottom edge, up the left edge, then repeat for the inner rectangle.

spiral-traversal-visual.txt
Matrix (3×4):
     ┌───────┬───────┬───────┬───────┐
     │  1  →│  2  →│  3  →│  4  │   Layer 1: top row (left to right)
     ├───────┼───────┼───────┼──│────┤
     │  5   │  6  →│  7   │  8↓ │   Layer 2 starts at 6,7 (inner)
     ├───────┼───────┼───────┼──│────┤
     │ ←10  │ ←11  │ ←12  │  9  │   Layer 1: bottom row (right to left)
     └───────┴───────┴───────┴───────┘
       ↑
     Layer 1: left column (bottom to top, but only element 5 remains)
 
Spiral order: 1 → 2 → 3 → 4 → 8 → 12 → 11 → 10 → 9 → 5 → 6 → 7
 
For a 3×4 matrix, after the outer layer, what remains is just [6, 7]

spiral-traversal.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def spiral_traversal(matrix):
    if not matrix or not matrix[0]:
        return []
    
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    
    while top <= bottom and left <= right:
        // 1. Traverse top row (left to right)
        for col in range(left, right + 1):
            result.append(matrix[top][col])
        top += 1  // Shrink top boundary
        
        // 2. Traverse right column (top to bottom)
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1  // Shrink right boundary
        
        // 3. Traverse bottom row (right to left) - if rows remain
        if top <= bottom:
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1  // Shrink bottom boundary
        
        // 4. Traverse left column (bottom to top) - if columns remain
        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1  // Shrink left boundary
    
    return result
 
// Example:
matrix = [[1,2,3,4], [5,6,7,8], [9,10,11,12]]
print(spiral_traversal(matrix))
// Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Boundary Conditions

Common Use Cases:

•Spiral print/flatten — Classic interview problem
•Image processing — Spiral blur or effect application
•Game mechanics — Spiral reveal of a game board
•Generating spiral matrices — Fill a matrix in spiral order

Boundary Traversal and Wave Patterns

Beyond spirals, there are other specialized traversal patterns worth knowing.

Boundary (Perimeter) Traversal:

Visit only the outer edge of the matrix:

boundary-traversal.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def boundary_traversal(matrix):
    if not matrix or not matrix[0]:
        return []
    
    rows, cols = len(matrix), len(matrix[0])
    result = []
    
    // Handle edge cases
    if rows == 1:
        return matrix[0][:]  // Single row
    if cols == 1:
        return [matrix[i][0] for i in range(rows)]  // Single column
    
    // Top row (all elements)
    for col in range(cols):
        result.append(matrix[0][col])
    
    // Right column (excluding top corner)
    for row in range(1, rows):
        result.append(matrix[row][cols-1])
    
    // Bottom row (excluding right corner, reversed)
    for col in range(cols-2, -1, -1):
        result.append(matrix[rows-1][col])
    
    // Left column (excluding both corners, reversed)
    for row in range(rows-2, 0, -1):
        result.append(matrix[row][0])
    
    return result
 
matrix = [[1,2,3], [4,5,6], [7,8,9]]
print(boundary_traversal(matrix))
// Output: [1, 2, 3, 6, 9, 8, 7, 4]  (excludes center 5)

Zigzag (Wave) Traversal:

Alternate direction on each row—go right on even rows, left on odd rows:

zigzag-traversal.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]
 
result = []
rows, cols = len(matrix), len(matrix[0])
 
for row in range(rows):
    if row % 2 == 0:
        // Even row: left to right
        for col in range(cols):
            result.append(matrix[row][col])
    else:
        // Odd row: right to left
        for col in range(cols - 1, -1, -1):
            result.append(matrix[row][col])
 
print(result)
// Output: [1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11, 12]
 
// Visual:
// Row 0: 1 → 2 → 3 → 4
// Row 1: 8 ← 7 ← 6 ← 5
// Row 2: 9 → 10 → 11 → 12

Diagonal Zigzag (Used in JPEG compression):

This pattern visits elements along successive diagonals, alternating direction:

diagonal-zigzag.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
// JPEG zigzag pattern for 8×8 block (simplified for 3×3)
matrix = [
    [0, 1, 5],
    [2, 4, 6],
    [3, 7, 8]
]
 
// Numbers show the visit order in zigzag:
// [0,0] → [0,1] → [1,0] → [2,0] → [1,1] → [0,2] → [1,2] → [2,1] → [2,2]
// Values: 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
 
// This is used because early diagonal values (low frequencies)
// are more important in image compression

Pattern Recognition

Neighbor Traversal: 4-Direction and 8-Direction

Many matrix algorithms need to access the neighbors of a cell. Understanding how to correctly enumerate neighbors is crucial for flood fill, pathfinding, image filters, and cellular automata.

4-Directional Neighbors (Cardinal Directions):

four-direction-neighbors.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 4-directional: up, down, left, right
// Direction vectors: (row_delta, col_delta)
DIRECTIONS_4 = [
    (-1, 0),  // Up
    (1, 0),   // Down
    (0, -1),  // Left
    (0, 1)    // Right
]
 
def get_4_neighbors(matrix, row, col):
    rows, cols = len(matrix), len(matrix[0])
    neighbors = []
    
    for dr, dc in DIRECTIONS_4:
        new_row, new_col = row + dr, col + dc
        // Check bounds
        if 0 <= new_row < rows and 0 <= new_col < cols:
            neighbors.append((new_row, new_col))
    
    return neighbors
 
// Example: neighbors of [1][1] in a 3×3 matrix
matrix = [[1,2,3], [4,5,6], [7,8,9]]
print(get_4_neighbors(matrix, 1, 1))
// Output: [(0,1), (2,1), (1,0), (1,2)] → cells with values 2, 8, 4, 6
 
// Corner case: neighbors of [0][0]
print(get_4_neighbors(matrix, 0, 0))
// Output: [(1,0), (0,1)] → only 2 neighbors (Down, Right)

8-Directional Neighbors (Including Diagonals):

eight-direction-neighbors.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 8-directional: includes diagonal neighbors
DIRECTIONS_8 = [
    (-1, 0),   // Up
    (1, 0),    // Down
    (0, -1),   // Left
    (0, 1),    // Right
    (-1, -1),  // Up-Left (diagonal)
    (-1, 1),   // Up-Right (diagonal)
    (1, -1),   // Down-Left (diagonal)
    (1, 1)     // Down-Right (diagonal)
]
 
def get_8_neighbors(matrix, row, col):
    rows, cols = len(matrix), len(matrix[0])
    neighbors = []
    
    for dr, dc in DIRECTIONS_8:
        new_row, new_col = row + dr, col + dc
        if 0 <= new_row < rows and 0 <= new_col < cols:
            neighbors.append((new_row, new_col))
    
    return neighbors
 
// Example: neighbors of [1][1] in a 3×3 matrix
matrix = [[1,2,3], [4,5,6], [7,8,9]]
print(get_8_neighbors(matrix, 1, 1))
// Output: All 8 surrounding cells (the center 5 is surrounded by 1-4, 6-9)
 
// Visualization:
//  [0,0] [0,1] [0,2]     1 2 3     ↖ ↑ ↗
//  [1,0] [1,1] [1,2]  =  4 5 6  =  ← ● →
//  [2,0] [2,1] [2,2]     7 8 9     ↙ ↓ ↘

Common Use Cases:

When to Use Each Neighbor Pattern
Pattern	Count	Use Cases
4-directional	Up to 4	Maze navigation, flood fill, BFS shortest path on grids
8-directional	Up to 8	Game of Life, image blur, unrestricted grid movement
Knight moves	Up to 8	Chess knight, specific jump patterns
Custom	Varies	Domain-specific movement rules

Always Check Bounds

Summary: Traversal Pattern Mastery

Key Takeaways

•Row-wise traversal — Outer loop on rows, inner on columns. Cache-optimal for row-major storage. Use for general element processing.
•Column-wise traversal — Outer loop on columns, inner on rows. Use for column-specific operations. Beware of cache inefficiency in row-major languages.
•Main diagonal — Elements where row == col. Use for trace, identity checks, diagonal games.
•Anti-diagonal — Elements where row + col is constant. Use for opposite diagonal checks and grouping.
•All diagonals — For main direction: row - col is constant. For anti-direction: row + col is constant.
•Spiral traversal — Layer-by-layer from outside in. Manage four boundaries carefully.
•Boundary traversal — Only the perimeter elements.
•Zigzag traversal — Alternating direction per row/diagonal.
•Neighbor traversal — 4-directional for cardinal directions, 8-directional including diagonals. Always validate bounds.

What's Next:

Page Complete

3 / 4