Algorithmic Strategies for Matrix

Introduction

Matrices (2D arrays) are fundamental data structures that appear frequently in coding interviews and real-world applications. The key to solving matrix problems efficiently is understanding spatial patterns, traversal techniques, and in-place manipulation strategies. This guide explores the most common approaches with real C# implementations from LeetCode problems.

Common Algorithmic Strategies

When approaching matrix problems, you’ll typically encounter these strategies:

• In-Place Manipulation: Modify the matrix without using extra space
• Spiral Traversal: Navigate matrices in circular patterns
• Depth-First Search (DFS): Explore matrix paths with backtracking
• Boundary Tracking: Use markers to track rows/columns with special properties

Strategy 1: In-Place Manipulation

In-Place Manipulation refers to algorithms that modify a data structure directly without using additional space proportional to the input size. For matrices, this means transforming elements by cleverly reusing the existing matrix space, often using the matrix itself as auxiliary storage through marking or swapping. This technique is crucial when space complexity constraints require O(1) extra space.

When to use it

• Space complexity must be O(1) or minimal
• Need to transform matrix without creating a copy
• Can use matrix elements themselves as markers
• Rotation, transposition, or element marking problems

Time Complexity: O(n²) or O(m·n) | Space Complexity: O(1)

Problem: Rotate Image

Rotate an n × n 2D matrix by 90 degrees clockwise in-place.

Implementation:

public class Solution
{
    public void Rotate(int[][] matrix)
    {
        int n = matrix.Length;

        // Rotate matrix 90 degrees clockwise by swapping elements in concentric layers
        for (int i = 0; i < n / 2; i++)
        {
            for (int j = i; j < n - i - 1; j++)
            {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = tmp;
            }
        }
    }
}

Key Insight: Rotate in layers from outside to inside. For each layer, swap 4 elements at a time in a circular fashion: top → right → bottom → left → top.

Visual Example:

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

Problem: Set Matrix Zeroes

Given an m × n matrix, if an element is 0, set its entire row and column to 0 in-place.

Implementation:

public class Solution
{
    public void SetZeroes(int[][] matrix)
    {
        int m = matrix.Length;
        int n = matrix[0].Length;

        bool[] row = new bool[m];
        bool[] col = new bool[n];

        // First pass: mark rows and columns that contain zeros
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                row[i] = row[i] || matrix[i][j] == 0;
                col[j] = col[j] || matrix[i][j] == 0;
            }
        }

        // Second pass: set elements to zero based on markers
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (row[i] || col[j])
                {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

Key Insight: Use two auxiliary arrays to track which rows and columns should be zeroed. This prevents accidentally using newly set zeros as indicators. Alternative: Use first row and column as markers for true O(1) space.

Brute Force Alternative: O(m·n) space

// Create a copy of the matrix
public void SetZeroes(int[][] matrix)
{
    int m = matrix.Length, n = matrix[0].Length;
    int[][] copy = new int[m][];
    
    for (int i = 0; i < m; i++)
    {
        copy[i] = new int[n];
        Array.Copy(matrix[i], copy[i], n);
    }
    
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (copy[i][j] == 0)
            {
                // Set entire row and column to 0
                for (int k = 0; k < n; k++) matrix[i][k] = 0;
                for (int k = 0; k < m; k++) matrix[k][j] = 0;
            }
        }
    }
}

Why In-Place is Better: Reduces O(m·n) extra space to O(m+n) or even O(1) by using the matrix itself for tracking.

Strategy 2: Spiral Traversal

Spiral Traversal is a technique for visiting all elements of a matrix in a spiral pattern: starting from the outer layer, moving right → down → left → up, then repeating for inner layers. This requires careful boundary management to avoid revisiting elements. The pattern is common in problems requiring sequential matrix processing or reshaping.

When to use it

• Need to traverse matrix in circular/spiral order
• Layer-by-layer processing required
• Converting 2D structure to 1D sequence
• Boundary conditions need careful handling

Time Complexity: O(m·n) | Space Complexity: O(1) or O(m·n) for output

Problem: Spiral Matrix

Return all elements of an m × n matrix in spiral order.

Implementation:

public class Solution
{
    public IList<int> SpiralOrder(int[][] matrix)
    {
        if (matrix.Length == 0 || matrix[0].Length == 0)
            return new List<int>();

        List<int> ans = new List<int>();
        int m = matrix.Length; 
        int n = matrix[0].Length;

        for (int i = 0; ans.Count < m * n; i++)
        {
            // Move right
            for (int j = i; j < n - i; j++)
                ans.Add(matrix[i][j]);

            // Move down
            for (int j = i + 1; j < m - i; j++)
                ans.Add(matrix[j][n - i - 1]);

            // Move left (if not single row)
            if (m - i - 1 != i)
            {
                for (int j = n - i - 2; j >= i; j--)
                    ans.Add(matrix[m - i - 1][j]);
            }

            // Move up (if not single column)
            if (n - i - 1 != i)
            {
                for (int j = m - i - 2; j > i; j--)
                    ans.Add(matrix[j][i]);
            }
        }

        return ans;
    }
}

Key Insight: Process matrix in concentric layers. For each layer, traverse: top row → right column → bottom row → left column. Check for single row/column to avoid duplicates.

Visual Example:

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

Brute Force Alternative: O(m·n) space

// Use a visited matrix to track processed elements
public IList<int> SpiralOrder(int[][] matrix)
{
    List<int> result = new List<int>();
    if (matrix.Length == 0) return result;
    
    int m = matrix.Length, n = matrix[0].Length;
    bool[][] visited = new bool[m][];
    for (int i = 0; i < m; i++) visited[i] = new bool[n];
    
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    int x = 0, y = 0, dir = 0;
    
    for (int i = 0; i < m * n; i++)
    {
        result.Add(matrix[x][y]);
        visited[x][y] = true;
        
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny])
        {
            dir = (dir + 1) % 4;
            nx = x + dx[dir];
            ny = y + dy[dir];
        }
        
        x = nx;
        y = ny;
    }
    
    return result;
}

Why Spiral is Better: Avoids O(m·n) visited array by using mathematical boundaries, reducing space to O(1) (excluding output).

Strategy 3: Depth-First Search (DFS)

Depth-First Search (DFS) in matrices explores paths by recursively visiting adjacent cells (up, down, left, right) until reaching a boundary or target condition. It’s often combined with backtracking - marking cells as visited during exploration and unmarking them afterwards to allow alternative paths. This technique is essential for pathfinding, word search, and connectivity problems in 2D grids.

When to use it

• Need to explore all possible paths
• Word/pattern search in matrix
• Finding connected components
• Backtracking required to try multiple paths

Time Complexity: O(m·n·4^k) where k is path length | Space Complexity: O(k) for recursion stack

Problem: Word Search

Given an m × n grid of characters, return true if the word exists in the grid. The word can be constructed from letters of adjacent cells (horizontally or vertically), and the same cell cannot be used more than once.

Implementation:

public class Solution
{
    public bool Exist(char[][] board, string word)
    {
        int m = board.Length;
        int n = board[0].Length;
        int[][] dirs = { 
            new int[] { 0, 1 },  // right
            new int[] { 0, -1 }, // left
            new int[] { 1, 0 },  // down
            new int[] { -1, 0 }  // up
        };

        bool DFS(int x, int y, int i)
        {
            // Boundary check and character match
            if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != word[i]) 
                return false;
            
            // Found complete word
            if (i + 1 == word.Length) 
                return true;

            char c = board[x][y];
            board[x][y] = '0'; // Mark as visited

            // Explore all 4 directions
            foreach (var dir in dirs)
            {
                if (DFS(x + dir[0], y + dir[1], i + 1)) 
                    return true;
            }

            board[x][y] = c; // Backtrack: restore original value
            return false;
        }

        // Try starting from each cell
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (DFS(i, j, 0)) 
                    return true;
            }
        }

        return false;
    }
}

Key Insight: Start DFS from each cell matching the first character. Mark visited cells temporarily by changing their value, then restore during backtracking. This allows trying all possible paths without extra space.

Optimization Note: The 4^k factor comes from potentially exploring 4 directions at each of k positions. Early termination when character doesn’t match prevents worst-case behavior in practice.

Brute Force Alternative: Generate all paths

// Generate all possible paths of length k and check against word
// This would be extremely inefficient: O(m·n·(m·n)^k)
public bool Exist(char[][] board, string word)
{
    // For each cell, try all possible paths of word.Length
    // Check if any path spells the word
    // This approach is impractical and would timeout
    // DFS with backtracking is the optimal approach
}

Why DFS is Better: Pruning invalid paths early through character matching and visited marking dramatically reduces the search space from exponential to manageable.

Strategy Selection Guide

Problem Type	Strategy	Time	Space
Rotate matrix 90°	In-Place Manipulation	O(n²)	O(1)
Set row/column to zero	In-Place (with markers)	O(m·n)	O(m+n) or O(1)
Traverse in spiral order	Spiral Traversal	O(m·n)	O(1)
Word search in grid	DFS + Backtracking	O(m·n·4^k)	O(k)
Find islands/components	DFS or BFS	O(m·n)	O(m·n)
Shortest path	BFS	O(m·n)	O(m·n)

Pattern Recognition Tips

1. Rotate/transpose matrix? → Think In-Place Manipulation with layer swapping
2. Read matrix in special order? → Think Spiral Traversal
3. Find path or pattern? → Think DFS with Backtracking
4. Need to mark rows/columns? → Think In-Place with first row/column as markers
5. Connected regions? → Think DFS or Union-Find
6. Shortest path? → Think BFS with queue

Common Matrix Patterns

Direction Vectors

// Four directions: right, down, left, up
int[][] dirs = {
    new int[] {0, 1},
    new int[] {1, 0},
    new int[] {0, -1},
    new int[] {-1, 0}
};

// Eight directions (including diagonals)
int[][] dirs8 = {
    new int[] {-1, -1}, new int[] {-1, 0}, new int[] {-1, 1},
    new int[] {0, -1},                      new int[] {0, 1},
    new int[] {1, -1},  new int[] {1, 0},  new int[] {1, 1}
};

Boundary Checking

bool IsValid(int x, int y, int m, int n)
{
    return x >= 0 && x < m && y >= 0 && y < n;
}

Layer Processing

// For n×n matrix, process n/2 layers
for (int layer = 0; layer < n / 2; layer++)
{
    int first = layer;
    int last = n - 1 - layer;
    // Process elements from first to last
}

Conclusion

Mastering matrix algorithms is essential for solving 2D grid problems efficiently. The key is to:

1. Identify the traversal pattern required (linear, spiral, DFS)
2. Optimize space by using in-place techniques when possible
3. Handle boundaries carefully to avoid index errors
4. Use backtracking for path exploration problems

Practice these strategies on LeetCode to build intuition for matrix manipulation. Understanding these patterns will help you quickly identify the optimal approach for any 2D grid problem you encounter. 🔲

References

LeetCode. (2024). Matrix Problems. https://leetcode.com/tag/matrix/

Cormen, T. H., Leiserson, C. E., Rivest, R. L. & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.). Springer.