∞

Algo Infinity Verse

Master the Matrix Data Structure 2D Arrays, Traversals & Real-World Applications

|
Start Learning Practice Exercises
0 Topics
0 Examples
0 Exercises

🔢 Learn Matrix

Master 2D arrays and matrix algorithms used in competitive programming and interviews.

0 / 5 topics completed
01

Introduction to Matrix

A Matrix is a 2D array arranged in rows and columns. It is one of the most versatile data structures, used in image processing, graph representation, dynamic programming, and much more. An M × N matrix has M rows and N columns.

Representation in Memory

In most languages, a matrix is stored as an array of arrays. Element at row i, column j is accessed as matrix[i][j] in O(1) time.

A 3×3 matrix: matrix[0][0] is top-left, matrix[2][2] is bottom-right.

Col 0 Col 1 Col 2
Row 0123
Row 1456
Row 2789
Python 
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

rows = len(matrix)
cols = len(matrix[0])
print(matrix[1][2])
Practice: Introduction

In a 4×5 matrix, what is the index of the element at the 3rd row and 4th column?

Answer: matrix[2][3]

Explanation: Arrays are 0-indexed. 3rd row → index 2, 4th column → index 3.

02

Traversal Techniques

Traversal is the foundation of matrix problems. The choice of traversal pattern directly determines your algorithm's correctness.

Row-by-Row (Linear) Traversal — O(M×N)

The most common pattern. Visit every element left-to-right, top-to-bottom.

Python 
def linear_traverse(matrix):
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            print(matrix[i][j], end=' ')
        print()

Diagonal Traversal

For an N×N matrix, the main diagonal elements satisfy i == j. The anti-diagonal elements satisfy i + j == N - 1.

Spiral Traversal

Traverse the matrix in a spiral order using four boundary pointers: top, bottom, left, right. Shrink boundaries after each pass.

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

    while top <= bottom and left <= right:
        for col in range(left, right + 1):
            result.append(matrix[top][col])
        top += 1
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1
        if top <= bottom:
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1
        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1
    return result
💡

For BFS/DFS on a matrix, use the 4-directional delta array: dirs = [(-1,0),(1,0),(0,-1),(0,1)]. For 8-directional, add the diagonals.

03

Common Operations

These operations appear repeatedly in interview problems. Know the in-place technique for each.

Transpose — O(N²)

Swap matrix[i][j] with matrix[j][i] for all i < j. Only valid for square matrices in-place.

Python 
def transpose(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

Rotate 90° Clockwise — O(N²)

Classic in-place trick: Transpose the matrix, then reverse each row. This avoids allocating extra space.

Python 
def rotate_90_cw(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()

Set Zeroes — O(M×N)

If an element is 0, set its entire row and column to 0. Key insight: record which rows/columns need zeroing before modifying, to avoid false propagation.

Practice: Operations

What is the result of transposing the matrix [[1,2],[3,4]]?

Answer: [[1,3],[2,4]]

Explanation: matrix[0][1]=2 swaps with matrix[1][0]=3. Row 0 becomes [1,3], Row 1 becomes [2,4].

04

Applications

Matrices appear in some of the most important algorithmic problems across domains.

1. Graph Representation (Adjacency Matrix)

An N×N boolean matrix where matrix[i][j] = 1 means there's an edge between node i and node j. Trade-off: O(1) edge lookup but O(N²) space.

2. Dynamic Programming

Many DP problems use a 2D table — Longest Common Subsequence, Edit Distance, Unique Paths. The matrix stores subproblem results for bottom-up computation.

3. Island / Flood Fill (BFS/DFS)

Grid problems like "Number of Islands" treat the matrix as a graph. DFS/BFS from each unvisited cell, marking visited cells to avoid re-processing.

4. Search in Sorted Matrix

In a matrix where rows and columns are sorted, start at the top-right corner. If target is smaller, move left; if larger, move down. This gives O(M+N) search.

💡

The "top-right corner" search trick is a favorite FAANG interview pattern. It eliminates one row or one column per step, giving optimal O(M+N) without binary search.

05

Practice Exercises

Test your understanding of matrix concepts.

Exercise 1: Spiral Matrix

Given matrix [[1,2,3],[4,5,6],[7,8,9]], what is the spiral order output?

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

Explanation: Top row left→right: 1,2,3. Right column top→bottom: 6,9. Bottom row right→left: 8,7. Left column bottom→top: 4. Center: 5.

Exercise 2: Rotate 90°

After rotating [[1,2],[3,4]] 90° clockwise in-place, what is the result?

Answer: [[3,1],[4,2]]

Explanation: Transpose → [[1,3],[2,4]]. Reverse each row → [[3,1],[4,2]].

Exercise 3: Search in Sorted Matrix

In matrix [[1,4,7],[2,5,8],[3,6,9]] (rows and columns sorted), how many steps does it take to find 6 using the top-right corner approach?

Answer: 3 steps

Start at top-right: matrix[0][2]=7. 6 < 7 → move left. matrix[0][1]=4. 6 > 4 → move down. matrix[1][1]=5. 6 > 5 → move down. matrix[2][1]=6. Found!