867. Transpose Matrix
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 62.0%
Problem Breakdown
The problem requires us to transpose a given 2D integer array matrix. Transposing a matrix involves flipping it over its main diagonal, which means that the rows and columns of the original matrix are swapped. The input is a 2D list where each sublist represents a row in the matrix. The output should be another 2D list representing the transposed matrix.
Inputs:
- A 2D integer array
matrixwith dimensionsm x n.
Outputs:
- A 2D integer array representing the transpose of the input matrix, with dimensions
n x m.
Implicit Constraints or Tricky Edge Cases:
- The matrix can be square (i.e.,
m == n) or rectangular (i.e.,m != n). - The matrix may contain negative numbers.
- The matrix could potentially have a size of up to 1000x1000, so the solution should be efficient in terms of both time and space.
Intuition
A brute-force approach would involve creating a new matrix with dimensions n x m and then iterating over each element of the original matrix to place it in its transposed position. This approach is straightforward but has a time complexity of O(m * n) and a space complexity of O(m * n), which is acceptable given the constraints.
However, a more efficient approach can be taken if we consider that the transpose operation can be performed in-place for square matrices (where m == n). For rectangular matrices, an out-of-place solution is necessary due to the change in dimensions. The key insight is to use list comprehensions or nested loops to construct the transposed matrix efficiently.
Approach
- Identify Dimensions: Determine the number of rows (
m) and columns (n) in the input matrix. - Create Transposed Matrix: Initialize a new 2D list with dimensions
n x m. - Populate Transposed Matrix: Use nested loops or list comprehensions to iterate over each element of the original matrix and place it in its transposed position in the new matrix.
- Return Result: Return the newly constructed transposed matrix.
Complexity Analysis
- Time Complexity: O(m * n), where
mis the number of rows andnis the number of columns in the input matrix. This is because we need to visit each element of the matrix once. - Space Complexity: O(m * n) for storing the transposed matrix, as we are creating a new 2D list with dimensions
n x m.
Solution
def transpose(matrix):
# Determine the number of rows and columns in the original matrix
m = len(matrix)
n = len(matrix[0])
# Initialize the transposed matrix with dimensions n x m
transposed_matrix = [[0] * m for _ in range(n)]
# Populate the transposed matrix
for i in range(m):
for j in range(n):
transposed_matrix[j][i] = matrix[i][j]
return transposed_matrix
Edge Cases Handled
- Square Matrix: The solution works correctly for matrices where the number of rows equals the number of columns.
- Rectangular Matrix: The solution handles cases where the number of rows is not equal to the number of columns, resulting in a change in dimensions for the transposed matrix.
- Single Row/Column Matrix: The solution correctly handles matrices with only one row or one column by swapping their dimensions.
- Empty Matrix: If the input matrix is empty (i.e.,
matrix == []), the function will return an empty list, as expected.