Jobs

Interviews

Discussions

Transpose Matrix

Easy

Asked by:

11 views

Topics:

Arrays

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 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⁹

Transpose Matrix

Easy

Asked by:

11 views

Topics:

Arrays

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 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⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the dimensions of the input matrix (number of rows and columns)? Can they be zero?
Can the input matrix be empty (i.e., have zero rows or columns), or can it contain null values? What should I return in such cases?
What is the data type of the elements within the matrix (e.g., integers, floats)? Are there any restrictions on the range of values these elements can take?
Is it guaranteed that the input matrix will always be rectangular (i.e., each row has the same number of columns)?
Should I perform the transposition in-place, modifying the original matrix, or should I create and return a new transposed matrix?

Brute Force Solution

Approach

The brute force method to transpose a matrix directly creates a new matrix. We fill the new matrix by taking each element from the original matrix and placing it in its transposed position in the new matrix.

Here's how the algorithm would work step-by-step:

Create a brand new empty matrix that has the dimensions swapped compared to the original. If the original had 3 rows and 4 columns, the new one will have 4 rows and 3 columns.
Go through each element in the original matrix, one by one.
For each element, find its row and column number in the original matrix.
In the new matrix, place that element at the position where the row number becomes the column number and the column number becomes the row number.
Continue this process for every element in the original matrix until the new transposed matrix is completely filled.
The new matrix is now the transpose of the original matrix.

Code Implementation

def transpose_matrix_brute_force(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    # Create the transposed matrix with dimensions swapped.
    transposed_matrix = [([0] * number_of_rows) for _ in range(number_of_columns)]

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):

            # Place each element in its transposed position.
            transposed_matrix[column_index][row_index] = matrix[row_index][column_index]

    return transposed_matrix

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each element of the original matrix to populate the transposed matrix. Let 'm' be the number of rows and 'n' be the number of columns in the original matrix. The algorithm visits each of the m*n elements in the original matrix exactly once. Therefore, the time complexity is directly proportional to the number of elements, resulting in O(m*n). If m and n are the same, it would simplify to O(n²).

Space Complexity

O(N*M) – The algorithm creates a new matrix to store the transposed result. The size of this new matrix is determined by the dimensions of the input matrix. Specifically, if the input matrix has N rows and M columns, the transposed matrix will have M rows and N columns. Therefore, the auxiliary space required is proportional to M*N, which we denote as O(N*M), where N is the number of rows and M is the number of columns in the original matrix.

Optimal Solution

Approach

The goal is to swap the rows and columns of the matrix. The core idea is to create a new matrix where the element at row 'i' and column 'j' in the original matrix becomes the element at row 'j' and column 'i' in the new matrix.

Here's how the algorithm would work step-by-step:

Figure out the dimensions of the original matrix (number of rows and columns).
Create a new matrix with the number of rows equal to the number of columns in the original matrix, and the number of columns equal to the number of rows in the original matrix.
Go through each element in the original matrix, one by one.
For each element, put it into its new corresponding location in the newly created matrix, effectively swapping its row and column position.
Once you've processed all the elements in the original matrix, the new matrix will be the transposed version.

Code Implementation

def transpose_matrix(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    # Create the transposed matrix with swapped dimensions.
    transposed_matrix = [([0] * number_of_rows) for _ in range(number_of_columns)]

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            # Populate transposed matrix by swapping row and column indices.
            transposed_matrix[column_index][row_index] = matrix[row_index][column_index]

    return transposed_matrix

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m*n) – The provided algorithm iterates through each element of the original matrix to perform the transposition. Let 'm' be the number of rows and 'n' be the number of columns of the input matrix. The algorithm accesses each element once, resulting in 'm * n' operations. Creating the new matrix is also proportional to m*n, where the transposed matrix has dimensions n*m, but that doesn't change the Big O. Therefore, the time complexity is O(m*n).

Space Complexity

O(N*M) – The algorithm creates a new matrix to store the transposed version of the original matrix. If the original matrix has dimensions N rows and M columns, the transposed matrix will have dimensions M rows and N columns. Therefore, the auxiliary space required to store the transposed matrix is proportional to N*M, where N is the number of rows and M is the number of columns in the original input matrix. Thus, the space complexity is O(N*M).

Edge Cases

Case	How to Handle
Null or undefined matrix input	Return an empty list or throw an IllegalArgumentException to indicate invalid input.
Empty matrix (matrix with zero rows)	Return an empty list as the transpose of an empty matrix is also an empty matrix.
Matrix with zero columns (all rows are empty)	Return an empty list as the transpose of a matrix with zero columns is also an empty matrix.
1x1 matrix (single element)	Return a new 1x1 matrix containing the same single element.
Non-rectangular matrix (rows have different lengths)	Throw an IllegalArgumentException or return null since a non-rectangular matrix cannot be transposed to a valid rectangular matrix.
Matrix with large dimensions (very large number of rows or columns)	Ensure the solution doesn't consume excessive memory by allocating the transposed matrix efficiently.
Matrix contains negative numbers, zeros, or large positive numbers	The basic transpose algorithm will work correctly with these value types without special handling.
Integer overflow during allocation when rows * cols exceeds maximum integer value	The number of rows multiplied by the number of columns can exceed the maximum integer value, so handle that by limiting the maximum matrix size.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the dimensions of the input matrix (number of rows and columns)? Can they be zero?
Can the input matrix be empty (i.e., have zero rows or columns), or can it contain null values? What should I return in such cases?
What is the data type of the elements within the matrix (e.g., integers, floats)? Are there any restrictions on the range of values these elements can take?
Is it guaranteed that the input matrix will always be rectangular (i.e., each row has the same number of columns)?
Should I perform the transposition in-place, modifying the original matrix, or should I create and return a new transposed matrix?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Create a brand new empty matrix that has the dimensions swapped compared to the original. If the original had 3 rows and 4 columns, the new one will have 4 rows and 3 columns.
Go through each element in the original matrix, one by one.
For each element, find its row and column number in the original matrix.
In the new matrix, place that element at the position where the row number becomes the column number and the column number becomes the row number.
Continue this process for every element in the original matrix until the new transposed matrix is completely filled.
The new matrix is now the transpose of the original matrix.

Code Implementation

def transpose_matrix_brute_force(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    # Create the transposed matrix with dimensions swapped.
    transposed_matrix = [([0] * number_of_rows) for _ in range(number_of_columns)]

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):

            # Place each element in its transposed position.
            transposed_matrix[column_index][row_index] = matrix[row_index][column_index]

    return transposed_matrix

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Figure out the dimensions of the original matrix (number of rows and columns).
Create a new matrix with the number of rows equal to the number of columns in the original matrix, and the number of columns equal to the number of rows in the original matrix.
Go through each element in the original matrix, one by one.
For each element, put it into its new corresponding location in the newly created matrix, effectively swapping its row and column position.
Once you've processed all the elements in the original matrix, the new matrix will be the transposed version.

Code Implementation

def transpose_matrix(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    # Create the transposed matrix with swapped dimensions.
    transposed_matrix = [([0] * number_of_rows) for _ in range(number_of_columns)]

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            # Populate transposed matrix by swapping row and column indices.
            transposed_matrix[column_index][row_index] = matrix[row_index][column_index]

    return transposed_matrix

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or undefined matrix input	Return an empty list or throw an IllegalArgumentException to indicate invalid input.
Empty matrix (matrix with zero rows)	Return an empty list as the transpose of an empty matrix is also an empty matrix.
Matrix with zero columns (all rows are empty)	Return an empty list as the transpose of a matrix with zero columns is also an empty matrix.
1x1 matrix (single element)	Return a new 1x1 matrix containing the same single element.
Non-rectangular matrix (rows have different lengths)	Throw an IllegalArgumentException or return null since a non-rectangular matrix cannot be transposed to a valid rectangular matrix.
Matrix with large dimensions (very large number of rows or columns)	Ensure the solution doesn't consume excessive memory by allocating the transposed matrix efficiently.
Matrix contains negative numbers, zeros, or large positive numbers	The basic transpose algorithm will work correctly with these value types without special handling.
Integer overflow during allocation when rows * cols exceeds maximum integer value	The number of rows multiplied by the number of columns can exceed the maximum integer value, so handle that by limiting the maximum matrix size.