122. Transpose a Matrix
Problem
Return the transpose of a rectangular matrix: original cell (r,c) becomes output cell (c,r). Do not mutate the input. An empty matrix or a matrix with zero columns transposes to an empty outer list.
Examples
Example 1
transpose([[1,2,3],[4,5,6]])
=> [[1, 4], [2, 5], [3, 6]]Rows and columns exchange roles.
Example 2
transpose([])
=> []There are no columns to become rows.
Example 3
transpose([[7]])
=> [[7]]The single coordinate maps to itself.
Reveal the worked solution and reasoning
Why this mechanism works
The transformation exchanges coordinate roles. Consequently the output has as many rows as the input has columns, and each output row is one complete original column. Deriving the dimensions first prevents a loop that works only for square inputs.
State and boundaries
output[c][r] receives matrix[r][c]. The output shape is cols by rows.
Protocol
- Determine row and column counts.
- Allocate cols independent rows of length rows.
- Copy each cell to exchanged coordinates.
- Return output.
Visualization
[1 2 3] [1 4]
[4 5 6] -> [2 5]
[3 6]Python implementation
def transpose(matrix):
rows = len(matrix)
cols = len(matrix[0]) if rows else 0
output = [[0] * rows for _ in range(cols)]
for r in range(rows):
for c in range(cols):
output[c][r] = matrix[r][c]
return output
Worked execution
transpose([[1,2,3],[4,5,6]])
L2 transpose: rows = len(matrix) matrix=[[1, 2, 3], [4, 5, 6]]; rows=2 L3 transpose: cols = len(matrix[0]) if rows else 0 matrix=[[1, 2, 3], [4, 5, 6]]; rows=2; cols=3 L4 transpose: output = [[0] * rows for _ in range(cols)] matrix=[[1, 2, 3], [4, 5, 6]]; rows=2; cols=3; _=0 L4 transpose: output = [[0] * rows for _ in range(cols)] matrix=[[1, 2, 3], [4, 5, 6]]; rows=2; cols=3; _=1 L4 transpose: output = [[0] * rows for _ in range(cols)] matrix=[[1, 2, 3], [4, 5, 6]]; rows=2; cols=3; _=2 L4 transpose: output = [[0] * rows for _ in range(cols)] matrix=[[1, 2, 3], [4, 5, 6]]; rows=2; cols=3; output=[[0, 0], [0, 0], [0, 0]] L5 transpose: for r in range(rows): matrix=[[1, 2, 3], [4, 5, 6]]; rows=2; cols=3; output=[[0, 0], [0, 0], [0, 0]]; r=0 L6 transpose: for c in range(cols): matrix=[[1, 2, 3], [4, 5, 6]]; rows=2; cols=3; output=[[0, 0], [0, 0], [0, 0]]; r=0; c=0 ... 8 intermediate state changes omitted ... L6 transpose: for c in range(cols): matrix=[[1, 2, 3], [4, 5, 6]]; rows=2; cols=3; output=[[1, 4], [2, 0], [3, 0]]; r=1; c=1 L7 transpose: output[c][r] = matrix[r][c] matrix=[[1, 2, 3], [4, 5, 6]]; rows=2; cols=3; output=[[1, 4], [2, 5], [3, 0]]; r=1; c=1 L6 transpose: for c in range(cols): matrix=[[1, 2, 3], [4, 5, 6]]; rows=2; cols=3; output=[[1, 4], [2, 5], [3, 0]]; r=1; c=2 L7 transpose: output[c][r] = matrix[r][c] matrix=[[1, 2, 3], [4, 5, 6]]; rows=2; cols=3; output=[[1, 4], [2, 5], [3, 6]]; r=1; c=2
Result: [[1, 4], [2, 5], [3, 6]]. Rows and columns exchange roles.
transpose([])
L2 transpose: rows = len(matrix) matrix=[]; rows=0 L3 transpose: cols = len(matrix[0]) if rows else 0 matrix=[]; rows=0; cols=0 L4 transpose: output = [[0] * rows for _ in range(cols)] matrix=[]; rows=0; cols=0; output=[]
Result: []. There are no columns to become rows.
Why the solution is correct
The coordinate exchange is a one-to-one mapping from input cells to output cells. Every cell is copied once to exactly its transposed position, preserving all values and producing the required dimensions.
Time and space
O(rows*cols) time and O(rows*cols) output space.
Common mistakes
Using [[0]*rows]*cols aliases output rows. Swapping entries in place is not a general rectangular transpose.
Reasoning card
State: output[c][r] receives matrix[r][c]. The output shape is cols by rows.
Invariant: output[c][r] equals input[r][c].
Decision to rehearse: Swap the roles of row and column in the output.
Finish: Return output
Transfer exercise
For nonempty rectangular matrices, verify that transposing twice restores the original values and shape.