Transpose Matrix

Easy Top 250

Associated Patterns

Interviewed At (Company Tags)

GoogleAmazon

Problem Description

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.

Examples

Example 1:

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

Example 2:

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

Constraints

m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 1000
1 ≤ m * n ≤ 10⁵
-10⁹ ≤ matrix[i][j] ≤ 10⁹

Swap Row and Column Dimensions

If the input matrix has dimension R x C, the transposed matrix will have dimension C x R.

We initialize a new grid of size C x R. We then copy the value at matrix[r][c] to result[c][r] for every row r and column c.

Solution: Dimension Swap

class Solution {
    public int[][] transpose(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] result = new int[cols][rows];

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                result[c][r] = matrix[r][c];
            }
        }
        return result;
    }
}

class Solution:
    def transpose(self, matrix: list[list[int]]) -> list[list[int]]:
        rows, cols = len(matrix), len(matrix[0])
        result = [[0] * rows for _ in range(cols)]

        for r in range(rows):
            for c in range(cols):
                result[c][r] = matrix[r][c]
                
        return result

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> transpose(std::vector<std::vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        std::vector<std::vector<int>> result(cols, std::vector<int>(rows));

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                result[c][r] = matrix[r][c];
            }
        }
        return result;
    }
};

Complexity Analysis:

Time Complexity: O(R * C) where R is the number of rows and C is the number of columns. We copy each element once.
Space Complexity: O(R * C) to store the transposed matrix.