Problem Description

The "Transpose Matrix" problem asks you to take a given 2D matrix and return its transpose. In mathematical terms, the transpose of a matrix is formed by turning its rows into columns and its columns into rows. For example, if you have a matrix matrix with r rows and c columns, the output should be a new matrix with c rows and r columns, where the value at position matrix[i][j] moves to position transposed[j][i].

Constraints:

• Each element in matrix is an integer.
• You must not reuse the same memory for the output; you must create a new matrix for the result.
• There is always one valid solution.
• Matrix dimensions can be any size, including non-square (e.g., 2x3, 3x1).

Thought Process

When first approaching this problem, you might think about how to "flip" the matrix over its diagonal. The most direct way is to create a new matrix and fill it by swapping rows and columns. For each element in the original matrix, you move it to the corresponding position in the new matrix.

A brute-force method would be to loop through every element and assign it to its new position. Since we're not required to do this in-place and must return a new matrix, this is both simple and efficient enough. There's no need for optimization using advanced data structures because access and assignment in arrays are already fast.

The key insight is recognizing that for each matrix[i][j], its position in the result is result[j][i].

Solution Approach

Let's walk through the step-by-step approach to transpose a matrix:

1. Determine the size of the input matrix: Let rows be the number of rows and cols be the number of columns in the input matrix.
2. Create a new matrix for the result: The transposed matrix will have cols rows and rows columns.
3. Iterate through the original matrix: For each element at position [i][j] in the original matrix, assign its value to position [j][i] in the new matrix.
4. Return the new matrix: After all elements are assigned, return the new matrix as the result.

This approach is efficient because it touches each element exactly once and does not require any extra data structures beyond the output matrix.

Example Walkthrough

Suppose we are given the following input matrix:

    matrix = [
      [1, 2, 3],
      [4, 5, 6]
    ]
  

This matrix has 2 rows and 3 columns. The transposed matrix should have 3 rows and 2 columns. Let's build it step by step:

• Start with an empty 3x2 matrix: result = [[_, _], [_, _], [_, _]]
• For i = 0 (first row):
  • j = 0: result[0][0] = matrix[0][0] = 1
  • j = 1: result[1][0] = matrix[0][1] = 2
  • j = 2: result[2][0] = matrix[0][2] = 3
• For i = 1 (second row):
  • j = 0: result[0][1] = matrix[1][0] = 4
  • j = 1: result[1][1] = matrix[1][1] = 5
  • j = 2: result[2][1] = matrix[1][2] = 6

Final transposed matrix:

    [
      [1, 4],
      [2, 5],
      [3, 6]
    ]
  

Each value from the original matrix has been placed in its transposed position.

Time and Space Complexity

Brute-force and Optimized Approach: In this problem, the brute-force method is already optimal.

• Time Complexity: O(M × N), where M is the number of rows and N is the number of columns. We visit each element of the matrix exactly once.
• Space Complexity: O(M × N), since we create a new matrix to store the transposed result. The size of the output is equal to the number of elements in the input.

There is no way to do better, as we must touch every element to move it to its new position.

Summary

The "Transpose Matrix" problem is a classic example of simple matrix manipulation. By understanding the relationship between the original and transposed positions of elements, we can efficiently build the transposed matrix in a single pass. The solution is direct, requires no advanced data structures, and has optimal time and space complexity. The elegance comes from recognizing the straightforward mapping between indices and implementing it cleanly.

Code Implementation

class Solution:
    def transpose(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        result = [[0] * rows for _ in range(cols)]
        for i in range(rows):
            for j in range(cols):
                result[j][i] = matrix[i][j]
        return result
      

class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& matrix) {
        int rows = matrix.size(), cols = matrix[0].size();
        vector<vector<int>> result(cols, vector<int>(rows));
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                result[j][i] = matrix[i][j];
            }
        }
        return result;
    }
};
      

class Solution {
    public int[][] transpose(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[][] result = new int[cols][rows];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                result[j][i] = matrix[i][j];
            }
        }
        return result;
    }
}
      

var transpose = function(matrix) {
    const rows = matrix.length, cols = matrix[0].length;
    const result = Array.from({length: cols}, () => Array(rows));
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            result[j][i] = matrix[i][j];
        }
    }
    return result;
};