Chapter 4 Matrix

4.0.1 Definition and Properties

4.0.1.1 Matrix Definition and Basic Properties

A matrix (plural: matrices) is a two-dimensional array of elements arranged in rows and columns. In coding interviews, matrices are typically represented as 2D arrays.

Key Properties:

  • Dimensions: An \(m \times n\) matrix has \(m\) rows and \(n\) columns
  • Indexing: Elements are accessed via row and column indices (0-indexed or 1-indexed depending on the context)
  • Square Matrix: A matrix where the number of rows equals the number of columns (\(m = n\))
  • Sparse Matrix: A matrix with many zero elements, often requiring special handling for memory efficiency
  • Dense Matrix: A matrix with mostly non-zero elements

Common Matrix Types:

  • Identity Matrix: Square matrix with 1s on the diagonal and 0s elsewhere
  • Diagonal Matrix: Non-zero elements only on the main diagonal
  • Symmetric Matrix: A square matrix that equals its transpose (\(A = A^T\))
  • Triangular Matrix: Upper triangular (zeros below diagonal) or lower triangular (zeros above diagonal)

4.0.2 Time and Space Complexity Considerations

For a matrix with \(m\) rows and \(n\) columns: - Full traversal: \(O(m \cdot n)\) time and space - Single row or column: \(O(\max(m, n))\) time and space - Most matrix algorithms require at least \(O(m \cdot n)\) time since every element may need inspection - In-place modifications can reduce space complexity from \(O(m \cdot n)\) to \(O(1)\) auxiliary space

4.0.3 Traversal Patterns

4.0.3.1 Row-wise and Column-wise Traversal

Row-wise (left to right, top to bottom):

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        process(matrix[i][j]);
    }
}

Column-wise (top to bottom, left to right):

for (int j = 0; j < n; j++) {
    for (int i = 0; i < m; i++) {
        process(matrix[i][j]);
    }
}

4.0.3.2 Spiral Traversal

Visit elements in a clockwise spiral pattern starting from the outside and moving inward. Commonly tested in interviews.

Key technique:

  • Maintain four boundaries: top, bottom, left, right
  • Traverse right along top boundary, then collapse top
  • Traverse down along right boundary, then collapse right
  • Traverse left along bottom boundary (if exists), then collapse bottom
  • Traverse up along left boundary (if exists), then collapse left
  • Repeat until boundaries cross

Time Complexity: \(O(m \cdot n)\) | Space Complexity: \(O(1)\) (excluding output)

See: Spiral Matrix for a complete implementation.

4.0.3.3 Diagonal Traversal

Visit elements along diagonals (top-left to bottom-right or other directions). Useful for certain problems.

Main diagonal: Elements where row index equals column index (\(i = j\)) Anti-diagonal: Elements where row index plus column index equals a constant (\(i + j = k\))

4.0.3.4 Boundary and Layer Traversal

Process matrices layer by layer from the outside inward (like peeling an onion).

Key technique:

  • Use similar boundary tracking as spiral traversal
  • Process one complete layer (top row, right column, bottom row, left column)
  • Shrink boundaries inward after each layer

Time Complexity: \(O(m \cdot n)\) | Space Complexity: \(O(1)\) (excluding output)

4.0.4 Transformation Operations

4.0.4.1 Matrix Transpose

Swap rows and columns: element at position \((i, j)\) moves to position \((j, i)\).

In-place transpose (square matrix only):

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        swap(matrix[i][j], matrix[j][i]);
    }
}

Key insight: Only swap upper triangle with lower triangle; diagonal remains unchanged.

4.0.4.2 Rotation

90° Clockwise Rotation:

  1. Transpose the matrix
  2. Reverse each row

90° Counter-clockwise Rotation:

  1. Transpose the matrix
  2. Reverse each column (or reverse the order of rows)

Key insight: For square matrices, rotation can be done in-place using layer-by-layer approach.

See: Rotate Image for a complete implementation.

4.0.4.3 Matrix Flip/Reflection

Horizontal flip (left-right):

  • Reverse each row independently

Vertical flip (top-bottom):

  • Reverse the order of rows

Time Complexity: \(O(m \cdot n)\) | Space Complexity: \(O(1)\) for in-place operations

4.0.5 Algorithmic Techniques

4.0.5.1 Depth-First Search (DFS) in Matrices

Explore connected components or paths in a matrix (e.g., finding islands, paths through cells).

Key considerations:

  • Track visited cells to avoid cycles
  • Use 4-directional neighbors (up, down, left, right) or 8-directional (including diagonals)
  • Base cases: out of bounds, already visited, or invalid cell
  • Recursion or explicit stack

Time Complexity: \(O(m \cdot n)\) | Space Complexity: \(O(m \cdot n)\) worst case (call stack)

See: Number of Islands, Surrounded Regions, Pacific Atlantic Water Flow for DFS implementations.

4.0.5.2 Breadth-First Search (BFS) in Matrices

Find shortest paths or explore level-by-level in a matrix.

Key considerations:

  • Use a queue for level-by-level traversal
  • Track visited cells to avoid reprocessing
  • Useful for finding shortest distance/path
  • Can track distance or parent pointers

Time Complexity: \(O(m \cdot n)\) | Space Complexity: \(O(m \cdot n)\) worst case (queue)

See: Rotting Oranges for a BFS implementation (multi-source variant below).

4.0.5.2.1 Multi-Source BFS

A powerful variation where BFS starts from multiple sources simultaneously rather than a single starting point. This technique is essential for problems involving simultaneous spreading, infection propagation, or finding distances from multiple origins.

Core Concept:

Instead of initializing the queue with one starting cell, add all source cells to the queue before starting the BFS traversal. All sources are treated as being at “distance 0” or “time 0”, and they spread outward in parallel.

Key Characteristics:

  1. Simultaneous propagation: All sources spread at the same rate, level by level
  2. Natural time tracking: Each BFS level represents one time unit (minute, hour, step)
  3. Shortest distance guarantee: First visit to a cell is always the shortest path from any source
  4. In-place marking: Can modify the matrix directly to track visited cells

Common Applications:

  • Infection/spreading problems: Rotting oranges, zombie outbreak, fire spread
  • Multi-facility distance: Distance to nearest hospital, police station, or landmark
  • Simultaneous flood fill: Water flowing from multiple sources
  • Game theory: Multiple players moving simultaneously

Standard Implementation Pattern:

public int multiSourceBFS(int[][] grid) {
    int rows = grid.length;
    int cols = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();

    // Phase 1: Multi-source initialization
    // Add ALL source cells to the queue
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == SOURCE_VALUE) {
                queue.offer(new int[]{i, j});
            }
        }
    }

    // Phase 2: Level-by-level BFS
    int time = 0;
    int[][] directions = {{-1,0}, {1,0}, {0,-1}, {0,1}};

    while (!queue.isEmpty()) {
        int size = queue.size();  // Current level size

        // Process all cells at current time/distance
        for (int k = 0; k < size; k++) {
            int[] cell = queue.poll();
            int r = cell[0], c = cell[1];

            // Explore 4 adjacent neighbors
            for (int[] dir : directions) {
                int nr = r + dir[0];
                int nc = c + dir[1];

                // Boundary check and validity check
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols)
                    continue;
                if (grid[nr][nc] != TARGET_VALUE)
                    continue;

                // Mark as visited and add to next level
                grid[nr][nc] = VISITED_VALUE;
                queue.offer(new int[]{nr, nc});
            }
        }

        // Increment time after processing entire level
        if (!queue.isEmpty())
            time++;
    }

    return time;
}

Two-Queue Approach for Time Tracking:

An alternative pattern uses two queues to explicitly separate current time step from next time step:

Queue<Cell> currMinQ = new LinkedList<>();  // Current time step
Queue<Cell> nextMinQ = new LinkedList<>();  // Next time step
int minutes = 0;

// Initialize currMinQ with all sources
// ... initialization code ...

while (!currMinQ.isEmpty()) {
    Cell cell = currMinQ.poll();

    // Process neighbors and add to nextMinQ
    for (int[] dir : directions) {
        // ... neighbor processing ...
        if (valid) {
            nextMinQ.offer(new Cell(ni, nj));
        }
    }

    // When current level exhausted, move to next level
    if (currMinQ.isEmpty() && !nextMinQ.isEmpty()) {
        minutes++;
        currMinQ = nextMinQ;
        nextMinQ = new LinkedList<>();
    }
}

Key Differences from Single-Source BFS:

Aspect Single-Source BFS Multi-Source BFS
Initialization Queue starts with 1 cell Queue starts with multiple cells
Distance/Time From one origin From nearest of all origins
Use Case Shortest path from point A to B Spread from multiple origins simultaneously
Example Maze solver Rotting oranges, fire spread

Time and Space Complexity:

  • Time: \(O(m \cdot n)\) - Each cell visited at most once
  • Space: \(O(m \cdot n)\) - Queue can contain up to all cells in worst case
  • Optimization: In-place marking can avoid separate visited array

Common Pitfalls:

  1. Forgetting to initialize all sources: Must add ALL sources before starting BFS
  2. Incorrect time tracking: Increment time only after processing complete level
  3. Not handling edge cases: Check for no sources, or already satisfied conditions
  4. Revisiting cells: Ensure cells are marked as visited when added to queue, not when polled

Example Problem Pattern (Rotting Oranges):

Initial grid (minute 0):     After minute 1:         After minute 2:
2 1 1                        2 2 1                   2 2 2
1 1 0         BFS →          2 1 0        BFS →      2 2 0
0 1 1                        0 1 1                   0 2 1

All cells with '2' start simultaneously spreading to adjacent '1' cells.
Time increments only when an entire level finishes processing.

Comparison with Other Patterns:

  • vs DFS: BFS guarantees shortest distance; DFS explores deeply first
  • vs Dijkstra: Multi-source BFS works when all edges have equal weight (1 step = 1 time unit)
  • vs Floyd-Warshall: Multi-source BFS is more efficient for sparse grids and specific source sets

Related Problems:

  • Walls and Gates - Distance to nearest gate using multi-source BFS
  • Rotting Oranges - Classic multi-source BFS with time tracking
  • 01 Matrix - Distance to nearest 0
  • As Far from Land as Possible - Maximum distance from all land cells

Time Complexity: \(O(m \cdot n)\) | Space Complexity: \(O(m \cdot n)\) worst case (queue)

4.0.5.3 Dynamic Programming on Matrices

Solve optimization problems like minimum path sum, maximum rectangle, edit distance problems.

Common DP approaches:

  • Top-down (memoization): Recursively compute with caching
  • Bottom-up (tabulation): Build solution table from smaller subproblems
  • Space optimization: Use rolling arrays to reduce space from \(O(m \cdot n)\) to \(O(n)\) or \(O(m)\)

Key insight: Matrix DP problems often require 1D or 2D DP tables.

4.0.5.4 Two-Pointer or Sliding Window in Matrices

Apply linear techniques to matrix rows/columns or use pointers for searching.

Common patterns:

  • Binary search on 2D sorted matrix (search rows or use space-filling curves)
  • Two pointers starting from opposite corners (e.g., top-right and bottom-left)
  • Sliding window on matrix rows for contiguous sub-matrix problems

4.0.5.5 Important Variations

Sorted Matrix Search:

  • If rows are sorted and columns are sorted, start from top-right corner
  • Move left if target is smaller, move down if target is larger

Rotated Matrix Search:

  • Identify which quadrant contains the target
  • Apply binary search on the identified section

Matrix Prefix Sum:

  • Precompute cumulative sums for fast range query
  • 2D prefix sum: \(\text{prefix}[i][j] = \text{prefix}[i-1][j] + \text{prefix}[i][j-1] - \text{prefix}[i-1][j-1] + \text{matrix}[i][j]\)