Domain 1EasyCORE

Transpose Matrix

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

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 matrix with dimensions m 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

  1. Identify Dimensions: Determine the number of rows (m) and columns (n) in the input matrix.
  2. Create Transposed Matrix: Initialize a new 2D list with dimensions n x m.
  3. 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.
  4. Return Result: Return the newly constructed transposed matrix.

Complexity Analysis

  • Time Complexity: O(m * n), where m is the number of rows and n is 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.