algoadvance

Given a 2D integer array matrix, return the transpose of matrix.

The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix’s row and column indices.

Example:

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

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

Clarifying Questions:

  1. Q: Is the input always a valid 2D list of integers, or do we need to handle invalid inputs? A: For this problem, you can assume that the input is always a valid matrix.

  2. Q: What are the constraints on the dimensions of the matrix? A: The dimensions of the matrix will be such that 1 <= rows, columns <= 1000.

  3. Q: Can the matrix be non-square? A: Yes, the matrix can have different numbers of rows and columns.

Strategy

  1. Initialize an Empty Matrix:
    • First, we’ll initialize a new matrix transpose with dimensions swapped. For example, if the input matrix is m x n, then the transposed matrix will be n x m.
  2. Populate the Transpose Matrix:
    • Iterate through the rows and columns of the original matrix.
    • For each element in the original matrix at position [i][j], place it in the transposed matrix at position [j][i].
  3. Return the Transposed Matrix.

Code

def transpose(matrix):
    # Getting the dimensions of the original matrix
    rows, cols = len(matrix), len(matrix[0])
    
    # Creating a new matrix with swapped dimensions
    transpose_matrix = [[0] * rows for _ in range(cols)]
    
    # Populating the transpose matrix
    for r in range(rows):
        for c in range(cols):
            transpose_matrix[c][r] = matrix[r][c]
    
    return transpose_matrix

# Test cases
print(transpose([[1,2,3],[4,5,6],[7,8,9]]))  # Output: [[1,4,7],[2,5,8],[3,6,9]]
print(transpose([[1,2,3],[4,5,6]]))         # Output: [[1,4],[2,5],[3,6]]

Time Complexity

The time complexity of this algorithm is O(m * n), where m is the number of rows and n is the number of columns. This is because we iterate through each element of the original matrix exactly once to build the transposed matrix.

The space complexity is O(m * n) as well because we are creating a new matrix to store the transpose with n rows and m columns.

Try our interview co-pilot at AlgoAdvance.com