Matrix Manipulation

She's full of layers. Handle her carefully, or you'll lose more than just a row or column.

How would you rotate an image? Let's say your image is just a 2D matrix of numbers, each cell representing a pixel in your image. This is an essential matrix problem. Before reading on, take some time to think about how you would solve it. A visual sketch on paper can be very helpful!

Problem: Rotate Image (LeetCode Link): You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). You must do this in-place, meaning you cannot use a second matrix. 💡 Hint

Key Techniques for Handling Matrices

Solving matrix problems in-place involves a specific set of skills. Knowing a few key "tricks" can save you a lot of time during interviews.

The "in-place" constraint often requires clever, multi-step approaches to avoid destroying the data you still need.

1. Matrix Traversal

The most fundamental operation is iterating through every cell. You can traverse row-by-row, column-by-column, or even diagonally, depending on the problem's needs.

matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]
ROWS, COLS = len(matrix), len(matrix[0])

# Row-by-row traversal
for r in range(ROWS):
  for c in range(COLS):
    # Access the element at matrix[r][c]
    print(matrix[r][c])

# Diagonal traversal (top-left to bottom-right)
for i in range(min(ROWS, COLS)): # Iterate up to the smaller dimension for main diagonal
    # Access the element at matrix[i][i]
    pass

int[][] matrix = {
  {1, 2, 3},
  {4, 5, 6},
  {7, 8, 9}
};
int ROWS = matrix.length;
int COLS = matrix[0].length;

// Row-by-row traversal
for (int r = 0; r < ROWS; r++) {
  for (int c = 0; c < COLS; c++) {
    // Access the element at matrix[r][c]
    System.out.println(matrix[r][c]);
  }
}

// Diagonal traversal (top-left to bottom-right)
for (int i = 0; i < Math.min(ROWS, COLS); i++) {
    // Access the element at matrix[i][i]
}

std::vector<std::vector<int>> matrix = {
  {1, 2, 3},
  {4, 5, 6},
  {7, 8, 9}
};
int ROWS = matrix.size();
int COLS = matrix[0].size();

// Row-by-row traversal
for (int r = 0; r < ROWS; r++) {
  for (int c = 0; c < COLS; c++) {
    // Access the element at matrix[r][c]
    std::cout << matrix[r][c] << std::endl;
  }
}

// Diagonal traversal (top-left to bottom-right)
for (int i = 0; i < std::min(ROWS, COLS); i++) {
    // Access the element at matrix[i][i]
}

2. In-Place vs. Extra Space

A frequent constraint in matrix problems is to modify the matrix "in-place," meaning you should do so without creating a new copy of the entire matrix. This is a memory-efficiency challenge that forces you to be clever about how you swap and update values without losing information you still need.

Walkthrough: The Trick to "Rotate Image"

The most elegant in-place solution for a 90-degree clockwise rotation is a two-step trick: Transpose, then Reverse.

Step 1: Transpose the Matrix

# Before Transpose:      After Transpose:
# [ 1, 2, 3 ]             [ 1, 4, 7 ]
# [ 4, 5, 6 ]             [ 2, 5, 8 ]
# [ 7, 8, 9 ]             [ 3, 6, 9 ]
def transpose(matrix):
    n = len(matrix)
    for r in range(n):
        for c in range(r + 1, n):  # Only swap above the diagonal
            matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]

// Before Transpose:      After Transpose:
// [ 1, 2, 3 ]             [ 1, 4, 7 ]
// [ 4, 5, 6 ]             [ 2, 5, 8 ]
// [ 7, 8, 9 ]             [ 3, 6, 9 ]
public void transpose(int[][] matrix) {
    int n = matrix.length;
    for (int r = 0; r < n; r++) {
        for (int c = r + 1; c < n; c++) { // Only swap above the diagonal
            int temp = matrix[r][c];
            matrix[r][c] = matrix[c][r];
            matrix[c][r] = temp;
        }
    }
}

// Before Transpose:      After Transpose:
// [ 1, 2, 3 ]             [ 1, 4, 7 ]
// [ 4, 5, 6 ]             [ 2, 5, 8 ]
// [ 7, 8, 9 ]             [ 3, 6, 9 ]
void transpose(std::vector<std::vector<int>>& matrix) {
    int n = matrix.size();
    for (int r = 0; r < n; r++) {
        for (int c = r + 1; c < n; c++) {
            std::swap(matrix[r][c], matrix[c][r]);
        }
    }
}

Step 2: Reverse Each Row

After transposing, you'll notice that each row of the transposed matrix is the reverse of what it should be in the final rotated matrix. The final step is to simply iterate through each row and reverse its elements.

# Before Reverse:        After Reverse:
# [ 1, 4, 7 ]             [ 7, 4, 1 ]
# [ 2, 5, 8 ]             [ 8, 5, 2 ]
# [ 3, 6, 9 ]             [ 9, 6, 3 ]
def reverse_rows(matrix):
    for row in matrix:
        row.reverse()

// Before Reverse:        After Reverse:
// [ 1, 4, 7 ]             [ 7, 4, 1 ]
// [ 2, 5, 8 ]             [ 8, 5, 2 ]
// [ 3, 6, 9 ]             [ 9, 6, 3 ]
public void reverseRows(int[][] matrix) {
    for (int[] row : matrix) {
        int left = 0, right = row.length - 1;
        while (left < right) {
            int temp = row[left];
            row[left] = row[right];
            row[right] = temp;
            left++;
            right--;
        }
    }
}

// Before Reverse:        After Reverse:
// [ 1, 4, 7 ]             [ 7, 4, 1 ]
// [ 2, 5, 8 ]             [ 8, 5, 2 ]
// [ 3, 6, 9 ]             [ 9, 6, 3 ]
void reverseRows(std::vector<std::vector<int>>& matrix) {
    for (auto& row : matrix) {
        std::reverse(row.begin(), row.end());
    }
}

This two-step process is a core "trick" worth remembering as it's far more intuitive than trying to calculate the final destination of each cell in one go.

Complexity Analysis

Time Complexity: $O(N^2)$ where N is the number of rows. We must visit each cell a constant number of times (once for the transpose and once for the reversal).
Space Complexity: Because the entire operation is performed "in-place," we use only a few temporary variables for swapping, resulting in constant extra space.

Advanced Techniques & More Problems

Once you've understood rotation, you can apply similar thinking to other complex traversal and in-place manipulation problems.

Using Cells as Markers

For some problems, you can avoid extra space by cleverly using the first row and column of the matrix itself as "markers" or flags. This is an advanced technique that demonstrates a deep understanding of in-place manipulation.

Problem: Set Matrix Zeroes (LeetCode Link) : Given an m x n integer matrix, if an element is 0, set its entire row and column to 0. You must do it in-place. 💡 Hint

Spiral Traversal

This involves managing four pointers (top, bottom, left, right) to trace the shrinking boundaries of the matrix as you traverse its outer layers.

Problem: Spiral Matrix (LeetCode Link) : Given an m x n matrix, return all elements of the matrix in spiral order.

Bonus: Matrix manipulation isn't just an interview problem; it's the heart of 2D graphics and image processing. Every time you resize, filter, or apply an effect to a photo, the software is performing millions of matrix operations on the underlying pixel grid.