867. Transpose Matrix

EasyArrayMatrixSimulation
Leetcode Link

Problem Description

The problem requires us to transpose a given 2D integer array, matrix. Transposing a matrix involves flipping the matrix over its main diagonal. This process converts rows to columns and vice versa, which leads to the interchange of the matrix's row and column indexes.

For example, let's consider a matrix as follows:

11 2 3
24 5 6

The main diagonal of this matrix is the set of elements that extend from the top left to the bottom right (elements 1 and 5 in this case).

When we transpose the matrix, the rows become columns, and the columns become rows. The transposed matrix will look like this:

11 4
22 5
33 6

The element that was originally at the second row, first column (4), is now at the first row, second column. The solution requires us to perform this operation on any given matrix and return the new transposed matrix.

Intuition

For the given solution, Python's built-in functions simplify the process of transposing a matrix. Here is the intuition behind the used approach:

  • The * operator, when used in the context of function argument unpacking, will unpack the argument list. For a 2D matrix, this effectively unpacks the rows of the matrix, making them available as individual arguments.

  • The zip function takes iterables (can be zero or more), aggregates them in a tuple, and returns it. When used with a 2D matrix unpacked into rows, zip essentially combines the elements of the rows that have the same index, thus forming the columns of the transposed matrix.

  • Finally, the list function converts the resulting tuples back into lists, as required for the solution. In Python, the zip function returns an iterator of tuples. To match the expected format of the solution, we convert each tuple into a list.

Putting these elements together, the single-line python code return list(zip(*matrix)) takes the original matrix, sends each row as a separate argument to zip, which pairs up the elements with the same index from each row, forming the new rows of the transposed matrix. These tuples are then converted into lists to get the final transposed matrix.

Solution Approach

Implementing the solution for transposing a matrix in Python is quite straightforward thanks to Python's powerful syntax and built-in functions. The provided reference solution uses almost no explicit algorithms because high-level function calls handle the necessary operations. Nevertheless, it's beneficial to break down the solution to understand the underlying patterns and behavior.

Here's the provided solution for reference:

1class Solution:
2    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
3        return list(zip(*matrix))

Let's walk through how it works, step by step:

  1. Function Argument Unpacking (* Operator):

    • The first step involves an advanced Python pattern called argument unpacking. In the expression zip(*matrix), the * operator is used to unpack the 2D matrix list.
    • Essentially, if the matrix is a list of lists like [ [a1, a2], [b1, b2], [c1, c2] ], calling zip(*matrix) is the same as calling zip([a1, a2], [b1, b2], [c1, c2]). Every individual list in matrix is passed as a separate argument to zip.
  2. zip Function:

    • The zip function takes any number of iterables and returns an iterator of tuples, where each tuple contains the i-th element from each of the input iterables.
    • When applied to rows of a matrix, zip effectively groups together the elements of the matrix by their column indices. For instance, a1 will be paired with b1 and c1, forming the first tuple of the new row in the transposed matrix.
  3. list Conversion:

    • The output from zip is an iterator of tuples. The list() function is used to convert these tuples into lists, as the problem expects a list of lists structure for the transposed matrix.

Since there is no nested loop or manual iteration, the entire operation is quite efficient. The actual transposition — the core algorithmic task — is completely delegated to the zip function, which is a built-in, highly optimized component of Python. The clever use of argument unpacking with * allows us to avoid manual index handling or iterating through rows and columns of the matrix, which would be needed in a more traditional, lower-level language solution.

Ultimately, this solution showcases the power of Python in terms of writing concise and readable code that leverages high-level functions and language features to perform complex operations with minimal code.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example to illustrate the solution approach. Consider the following 2D integer array, matrix:

1matrix = [
2    [1, 2, 3],
3    [4, 5, 6]
4]

We want to transpose this matrix, which will result in flipping the matrix over its main diagonal. To do this, we'll apply the steps in the solution approach.

  1. Function Argument Unpacking (* Operator):

    • We use the * operator to unpack the matrix's rows as arguments to the zip function. We can visualize this step as taking the two rows [1, 2, 3] and [4, 5, 6] and unpacking them such that they're passed to zip like zip([1, 2, 3], [4, 5, 6]).
  2. zip Function:

    • The zip function then takes these two lists and pairs elements at the same positions together, resulting in tuples. The output of zip given our two rows would be an iterator that generates the following tuples one by one: (1, 4), (2, 5), (3, 6).
    • These tuples represent the rows of the new, transposed matrix. The first tuple (1, 4) will be the first row, the second tuple (2, 5) will be the second row, and so on.
  3. list Conversion:

    • Next, we convert each of these tuples back into lists using the list function since the expected output format is a list of lists.
    • Applying the list function to the iterator of tuples from zip, we obtain the transposed matrix as a list of lists: [[1, 4], [2, 5], [3, 6]].

After going through the steps with our example matrix, the final transposed matrix is:

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

This walkthrough demonstrates how the provided Python solution transposes a matrix efficiently by utilizing function argument unpacking, the zip function, and list conversion to transform the matrix's rows into the transposed matrix's columns. The elegance of the solution lies in its simplicity and effective use of Python's built-in functionality to accomplish the task with a single line of code.

Solution Implementation

1# Import typing module to use type hints
2from typing import List
3
4class Solution:
5    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
6        # Transpose the input matrix.
7        # This is done by unpacking the rows of the matrix as arguments to the zip function.
8        # zip(*matrix) couples elements with the same index from each row together, effectively transposing the elements.
9        # Then, the zip object is converted into a list of lists, which is the transposed matrix.
10        transposed_matrix = [list(row) for row in zip(*matrix)]
11      
12        # Return the transposed matrix.
13        return transposed_matrix
14
1class Solution {
2  
3    // Function to transpose a given matrix
4    public int[][] transpose(int[][] matrix) {
5        // 'rows' is the number of rows in the input matrix
6        int rows = matrix.length;
7        // 'cols' is the number of columns in the input matrix which is derived from the first row
8        int cols = matrix[0].length;
9      
10        // 'transposedMatrix' is the transposed matrix where the rows and columns are swapped
11        int[][] transposedMatrix = new int[cols][rows];
12      
13        // Iterate over each column of the transposed matrix
14        for (int i = 0; i < cols; i++) {
15            // Iterate over each row of the transposed matrix
16            for (int j = 0; j < rows; j++) {
17                // Assign the value from the original matrix to the correct position in the transposed matrix
18                transposedMatrix[i][j] = matrix[j][i];
19            }
20        }
21        // Return the transposed matrix
22        return transposedMatrix;
23    }
24}
25
1#include <vector> // Include vector from Standard Template Library (STL)
2
3// Solution class
4class Solution {
5public:
6    // Function to transpose a given matrix
7    // @param originalMatrix: the original matrix to be transposed
8    // @return: a new matrix which is the transpose of the original matrix
9    vector<vector<int>> transpose(vector<vector<int>>& originalMatrix) {
10        int rowCount = originalMatrix.size();      // Number of rows in the matrix
11        int columnCount = originalMatrix[0].size(); // Number of columns in the matrix
12      
13        // Create a new matrix with dimensions swapped (columns x rows)
14        vector<vector<int>> transposedMatrix(columnCount, vector<int>(rowCount));
15      
16        // Iterate over each element in the new matrix
17        for (int i = 0; i < columnCount; ++i) {
18            for (int j = 0; j < rowCount; ++j) {
19                // Assign the value from the original matrix to the new position 
20                // in the transposed matrix by swapping indices
21                transposedMatrix[i][j] = originalMatrix[j][i];
22            }
23        }
24        return transposedMatrix; // Return the transposed matrix
25    }
26};
27
1/**
2 * Transposes a given matrix (converts rows to columns and vice versa).
3 * @param {number[][]} matrix The matrix to be transposed.
4 * @return {number[][]} The transposed matrix.
5 */
6function transpose(matrix: number[][]): number[][] {
7    // Get the number of rows in the matrix.
8    const rowCount: number = matrix.length;
9    // Get the number of columns in the matrix.
10    const columnCount: number = matrix[0].length;
11  
12    // Initialize a new matrix with dimensions swapped (rows become columns and vice versa).
13    const transposedMatrix: number[][] = new Array(columnCount)
14        .fill(0)
15        .map(() => new Array(rowCount).fill(0));
16  
17    // Iterate over each column of the new transposed matrix.
18    for (let i: number = 0; i < columnCount; ++i) {
19        // Iterate over each row of the new transposed matrix.
20        for (let j: number = 0; j < rowCount; ++j) {
21            // Assign the transposed value from the original matrix to the new matrix.
22            transposedMatrix[i][j] = matrix[j][i];
23        }
24    }
25
26    // Return the newly formed transposed matrix.
27    return transposedMatrix;
28}
29

Time and Space Complexity

The provided code receives a matrix and transposes it using Python's built-in zip function combined with argument unpacking (*).

Time Complexity:

The time complexity for transposing a matrix involves iterating over each element exactly once. In this code, zip takes m sequences (rows), where m is the number of rows of the matrix, and combines them into n tuples, where n is the number of columns. Since each element is touched once during the operation, the time complexity is O(m*n) where m is the number of rows and n is the number of columns in the original matrix.

Space Complexity:

The zip function creates n tuples (where n is the number of columns of the input matrix), each containing m elements (where m is the number of rows of the input matrix), and list() then converts these tuples into lists. This operation creates a new list of lists with the same number of elements as the original matrix. Therefore, the space complexity is also O(m*n), as it requires additional space proportional to the size of the input matrix.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄