Pular para o conteúdo principal

Transpose Matrix

Given a 2D matrix nums, return the matrix transposed.

Note: The transpose of a matrix is an operation that flips each value in the matrix across its main diagonal. In other words, the element at row i and column j in the original matrix becomes the element at row j and column i in the transposed matrix.

Example(s)​

Example 1:

Input: nums = [
  [1, 2],
  [3, 4]
]

Output: [
  [1, 3],
  [2, 4]
]

Explanation:
Original:    Transposed:
[1, 2]       [1, 3]
[3, 4]   →   [2, 4]

Element (0,0) stays at (0,0)
Element (0,1) moves to (1,0)
Element (1,0) moves to (0,1)
Element (1,1) stays at (1,1)

Example 2:

Input: nums = [
  [1, 2, 3],
  [4, 5, 6]
]

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

Explanation:
Original:       Transposed:
[1, 2, 3]       [1, 4]
[4, 5, 6]   →   [2, 5]
                 [3, 6]

Example 3:

Input: nums = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

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

Solution​

The solution creates a new matrix with swapped dimensions:

  1. Create result matrix: New matrix with dimensions swapped (rows ↔ columns)
  2. Copy elements: For each element at (i, j), place it at (j, i) in the result
  3. Return result: Return the transposed matrix

JavaScript Solution

/**
* Transpose a matrix
* @param {number[][]} matrix - 2D matrix to transpose
* @return {number[][]} - Transposed matrix
*/
function transpose(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;

// Create result matrix with swapped dimensions
const result = Array(cols).fill().map(() => Array(rows).fill(0));

// Copy elements: matrix[i][j] → result[j][i]
for (let i = 0; i < rows; i++) {
  for (let j = 0; j < cols; j++) {
    result[j][i] = matrix[i][j];
  }
}

return result;
}

// Test cases
const matrix1 = [
[1, 2],
[3, 4]
];
console.log('Example 1:', transpose(matrix1));
// [[1, 3], [2, 4]]

const matrix2 = [
[1, 2, 3],
[4, 5, 6]
];
console.log('Example 2:', transpose(matrix2));
// [[1, 4], [2, 5], [3, 6]]

const matrix3 = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
console.log('Example 3:', transpose(matrix3));
// [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (List Comprehension - Python)​

Here's a more concise Python solution using list comprehension:

def transpose_listcomp(matrix: List[List[int]]) -> List[List[int]]:
    """
    Transpose using list comprehension
    """
    return [[matrix[i][j] for i in range(len(matrix))] 
            for j in range(len(matrix[0]))]

Alternative: In-Place for Square Matrices​

For square matrices, we can transpose in-place:

/**
 * In-place transpose (only works for square matrices)
 */
function transposeInPlace(matrix) {
  const n = matrix.length;
  
  // Only swap upper triangle to avoid double swapping
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      // Swap matrix[i][j] with matrix[j][i]
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
  
  return matrix;
}

Complexity​

  • Time Complexity: O(m × n) - Where m is the number of rows and n is the number of columns. We need to visit each element once.
  • Space Complexity:
    • New matrix approach: O(m × n) - For the result matrix
    • In-place approach: O(1) - Only for square matrices

Approach​

The solution creates a new matrix with swapped dimensions:

  1. Get dimensions:

    • Original: rows × cols
    • Transposed: cols × rows

  2. Create result matrix:

    • Initialize a cols × rows matrix

  3. Copy elements:

    • For each element at position (i, j) in original
    • Place it at position (j, i) in result
    • Formula: result[j][i] = matrix[i][j]

  4. Return result:

    • Return the transposed matrix

Key Insights​

  • Swap dimensions: Rows become columns, columns become rows
  • Index swap: Element at (i, j) goes to (j, i)
  • New matrix: Typically creates a new matrix (unless square and in-place)
  • Simple operation: Straightforward element copying
  • O(m×n) time: Must visit all elements

Step-by-Step Example​

Let's trace through Example 1: matrix = [[1,2],[3,4]]

Original matrix:
  [1, 2]
  [3, 4]
  
Dimensions: 2 rows × 2 columns

Step 1: Create result matrix (2×2)
  result = [[0, 0], [0, 0]]

Step 2: Copy elements
  i=0, j=0: matrix[0][0] = 1 → result[0][0] = 1
  i=0, j=1: matrix[0][1] = 2 → result[1][0] = 2
  i=1, j=0: matrix[1][0] = 3 → result[0][1] = 3
  i=1, j=1: matrix[1][1] = 4 → result[1][1] = 4

Result:
  [1, 3]
  [2, 4]

Visual Representation​

Original:        Transpose:
[1, 2]           [1, 3]
[3, 4]       →   [2, 4]

Element mapping:
(0,0) → (0,0)    (0,1) → (1,0)
(1,0) → (0,1)    (1,1) → (1,1)

Main diagonal stays the same for square matrices.

Edge Cases​

  • Square matrix: Works correctly, dimensions stay the same
  • Rectangular matrix: Dimensions swap (m×n becomes n×m)
  • Single row: Becomes single column
  • Single column: Becomes single row
  • 1×1 matrix: Stays the same
  • Empty matrix: Handle gracefully

Important Notes​

  • Dimensions swap: m×n matrix becomes n×m matrix
  • Index swap: (i, j) → (j, i)
  • New matrix: Typically creates a new matrix
  • In-place: Only possible for square matrices
  • Main diagonal: Elements on main diagonal stay in place (for square matrices)

Mathematical Properties​

  • Double transpose: Transposing twice returns original matrix
  • Symmetric matrix: A matrix equal to its transpose
  • Identity matrix: Transpose of identity is identity
  • Matrix multiplication: (AB)ᵀ = BᵀAᵀ
  • Rotate Image: 90-degree rotation (uses transpose + reverse)
  • Spiral Matrix: Different matrix operation
  • Set Matrix Zeroes: Matrix modification
  • Valid Sudoku: Matrix validation

Takeaways​

  • Simple operation: Just swap indices (i, j) → (j, i)
  • Dimensions swap: Rows and columns exchange
  • New matrix: Typically need to create new matrix
  • O(m×n) time: Must process all elements
  • In-place possible: Only for square matrices