LeetCode Problem 867

Difficulty: 🟢 Easy
Topics: Array, Matrix, Simulation

Solution

LeetCode 867, Transpose Matrix

Problem Understanding

This problem asks us to compute the transpose of a given two dimensional matrix. A transpose operation flips a matrix across its main diagonal. In practical terms, every element at position (row, column) in the original matrix becomes the element at position (column, row) in the transposed matrix.

If the input matrix has m rows and n columns, then the resulting matrix will have n rows and m columns. This dimension swap is one of the most important observations in the problem.

For example, consider the matrix:

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

This matrix has 2 rows and 3 columns. After transposition, the rows become columns:

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

The input represents a valid rectangular matrix, meaning every row has the same number of columns. The problem guarantees:

• 1 <= m, n <= 1000
• 1 <= m * n <= 10^5

These constraints tell us several important things:

• The matrix can be large, up to one hundred thousand total elements.
• An O(m * n) solution is expected and efficient enough.
• Any significantly slower approach would be unnecessary.
• Because the output itself contains m * n elements, we must at least touch every value once.

The problem also guarantees that the matrix is non empty, so we do not need to handle completely empty input. However, there are still several important edge cases to consider:

• A single row matrix
• A single column matrix
• A square matrix
• A rectangular matrix where rows and columns differ
• Negative numbers and zero values

A naive implementation can easily make mistakes with dimensions, especially when allocating the result matrix.

Approaches

Brute Force Approach

The brute force idea is straightforward. We create a new matrix with swapped dimensions, then iterate through every element in the original matrix and place it into its transposed position.

For every position (i, j) in the original matrix:

result[j][i] = matrix[i][j]

This works because transposition directly swaps row and column indices.

Although this approach is already efficient enough for the problem constraints, it can still be considered brute force because it mechanically processes every element without any optimization or deeper structural trick.

The algorithm is correct because every original element is copied exactly once into its mathematically correct transposed position.

Optimal Approach

The key observation is that transposition is simply an index swap operation. There is no need for extra computation, sorting, or complex data structures.

The optimal solution creates a result matrix of size n x m and fills it directly using the rule:

transposed[col][row] = original[row][col]

Since every element must appear in the output exactly once, we cannot do better than visiting all elements. Therefore, O(m * n) is both necessary and optimal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n)	O(m * n)	Copies every element into a new matrix
Optimal	O(m * n)	O(m * n)	Direct index swapping with minimal overhead

Algorithm Walkthrough

1. Determine the dimensions of the original matrix.

Let:

• rows = len(matrix)
• cols = len(matrix[0])

This is necessary because the transposed matrix will reverse these dimensions. 2. Create the result matrix with swapped dimensions.

The transposed matrix must contain:

• cols rows
• rows columns

We initialize a matrix filled with zeros:

result = [[0] * rows for _ in range(cols)]

3. Iterate through every element in the original matrix.

Use nested loops:

• Outer loop iterates over rows
• Inner loop iterates over columns

4. Place each value into its transposed position.

For every element:

result[j][i] = matrix[i][j]

This swaps the row and column indices. 5. Return the completed transposed matrix.

Why it works

The transpose operation is defined mathematically as swapping row and column coordinates. Every element at position (i, j) in the original matrix is moved to (j, i) in the result matrix. Since the algorithm applies this transformation exactly once for every element, the final matrix is guaranteed to be the correct transpose.

Python Solution

from typing import List

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        rows = len(matrix)
        cols = len(matrix[0])

        transposed = [[0] * rows for _ in range(cols)]

        for row in range(rows):
            for col in range(cols):
                transposed[col][row] = matrix[row][col]

        return transposed

The implementation begins by determining the number of rows and columns in the original matrix. This information is required because the dimensions of the transposed matrix are reversed.

Next, the solution allocates a new matrix called transposed. Its dimensions are cols x rows, ensuring that every transposed coordinate is valid.

The nested loops visit every element exactly once. For each value at position (row, col), the algorithm stores it at (col, row) in the result matrix.

Finally, the completed transposed matrix is returned.

Go Solution

func transpose(matrix [][]int) [][]int {
    rows := len(matrix)
    cols := len(matrix[0])

    transposed := make([][]int, cols)

    for i := 0; i < cols; i++ {
        transposed[i] = make([]int, rows)
    }

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            transposed[col][row] = matrix[row][col]
        }
    }

    return transposed
}

The Go implementation follows the same algorithmic structure as the Python solution. The primary difference is how slices are allocated.

In Go, we first create the outer slice with make([][]int, cols), then allocate each inner slice individually. This ensures the transposed matrix has the correct dimensions.

Since the problem constraints fit comfortably within Go's integer range, integer overflow is not a concern here.

Worked Examples

Example 1

Input:

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

Initial dimensions:

• rows = 3
• cols = 3

Initialize result matrix:

[
  [0,0,0],
  [0,0,0],
  [0,0,0]
]

Processing steps:

Current Element	Original Position	New Position	Result Matrix
1	(0,0)	(0,0)	[[1,0,0],[0,0,0],[0,0,0]]
2	(0,1)	(1,0)	[[1,0,0],[2,0,0],[0,0,0]]
3	(0,2)	(2,0)	[[1,0,0],[2,0,0],[3,0,0]]
4	(1,0)	(0,1)	[[1,4,0],[2,0,0],[3,0,0]]
5	(1,1)	(1,1)	[[1,4,0],[2,5,0],[3,0,0]]
6	(1,2)	(2,1)	[[1,4,0],[2,5,0],[3,6,0]]
7	(2,0)	(0,2)	[[1,4,7],[2,5,0],[3,6,0]]
8	(2,1)	(1,2)	[[1,4,7],[2,5,8],[3,6,0]]
9	(2,2)	(2,2)	[[1,4,7],[2,5,8],[3,6,9]]

Final output:

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

Example 2

Input:

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

Initial dimensions:

• rows = 2
• cols = 3

Initialize result matrix:

[
  [0,0],
  [0,0],
  [0,0]
]

Processing steps:

Current Element	Original Position	New Position	Result Matrix
1	(0,0)	(0,0)	[[1,0],[0,0],[0,0]]
2	(0,1)	(1,0)	[[1,0],[2,0],[0,0]]
3	(0,2)	(2,0)	[[1,0],[2,0],[3,0]]
4	(1,0)	(0,1)	[[1,4],[2,0],[3,0]]
5	(1,1)	(1,1)	[[1,4],[2,5],[3,0]]
6	(1,2)	(2,1)	[[1,4],[2,5],[3,6]]

Final output:

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n)	Every element is visited exactly once
Space	O(m * n)	A new transposed matrix is allocated

The time complexity is optimal because the algorithm must inspect every element in the input matrix at least once. The space complexity is also unavoidable because the output itself contains m * n elements.

Test Cases

from typing import List

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        rows = len(matrix)
        cols = len(matrix[0])

        transposed = [[0] * rows for _ in range(cols)]

        for row in range(rows):
            for col in range(cols):
                transposed[col][row] = matrix[row][col]

        return transposed

solution = Solution()

assert solution.transpose([[1,2,3],[4,5,6],[7,8,9]]) == [
    [1,4,7],
    [2,5,8],
    [3,6,9]
]  # square matrix

assert solution.transpose([[1,2,3],[4,5,6]]) == [
    [1,4],
    [2,5],
    [3,6]
]  # rectangular matrix

assert solution.transpose([[1]]) == [
    [1]
]  # single element matrix

assert solution.transpose([[1,2,3]]) == [
    [1],
    [2],
    [3]
]  # single row matrix

assert solution.transpose([[1],[2],[3]]) == [
    [1,2,3]
]  # single column matrix

assert solution.transpose([[0,-1],[-2,3]]) == [
    [0,-2],
    [-1,3]
]  # negative numbers and zero

assert solution.transpose([[5,6],[7,8],[9,10]]) == [
    [5,7,9],
    [6,8,10]
]  # taller rectangular matrix

Test	Why
[[1,2,3],[4,5,6],[7,8,9]]	Validates standard square matrix transpose
[[1,2,3],[4,5,6]]	Validates rectangular matrix handling
[[1]]	Tests smallest possible matrix
[[1,2,3]]	Tests single row conversion into column
[[1],[2],[3]]	Tests single column conversion into row
[[0,-1],[-2,3]]	Confirms handling of negatives and zero
[[5,6],[7,8],[9,10]]	Tests non square matrix with more rows

Edge Cases

A single row matrix is an important edge case because the transpose becomes a column vector. Incorrect dimension handling can easily produce index errors. The implementation handles this correctly by allocating the result matrix with swapped dimensions before copying values.

A single column matrix is another important case. Here, the transpose becomes a single row. Some incorrect solutions accidentally preserve the original shape instead of swapping dimensions. This implementation explicitly constructs a cols x rows matrix, so the transformation is always correct.

Rectangular matrices are often the biggest source of bugs because row and column counts differ. A solution that assumes a square matrix will fail when dimensions are not equal. The implementation avoids this issue by independently tracking rows and cols and using them consistently throughout the algorithm.

Negative numbers and zero values are also worth considering. Since the algorithm only repositions values and never modifies them, all integers are preserved exactly during transposition.