# Transpose Matrix

## 1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?
• Can the input grid be blank??
• Let’s assume the grid is not blank. We don’t need to consider empty inputs.
• Can the row size be different from the column size?
• Yes, the row size can be different from the column size.
• What are the time and space constraints?
• Time complexity should be `O(m*n)`, m being the rows of the matrix and n being the columns of matrix. Space complexity should be `O(m*n)` too.
``````HAPPY CASE
Input: matrix = [[2,4,-1],[-10,5,11],[18,-7,6]]
Output: [[2,-10,18],[4,5,-7],[-1,11,6]]`````` ``````Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

EDGE CASE

Input: matrix = []
Output: []``````

## 2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For 2D-Array, common solution patterns include:

• Perform a BFS/DFS Search through the 2D Array
• A search through the 2D Array (either BFS or DFS) does not help us. We are transposing, not searching.
• Hash the 2D Array in some way to help with the Strings
• Hashing would not help us transpose this array
• Create/Utilize a Trie
• A Trie would not help us much in this problem since we are not trying to determine anything about a sequence of characters.

## 3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Solution 1:

General Idea: Use a zip function to gather all the first elements together and form a group, and so forth. i.e. [1, 2, 3] and [10, 20, 30] and returns (1, 10), (2, 20), (3, 30)

``Use zip function on the unpacked matrix array, to gather the first elements together and form a group and so forth. ``

Solution 2:

General Idea: Use list comprehension to access the column, to gather elements in row by column

``Use list comprehension to access the column, to gather elements in row by column``

Solution 3:

General Idea: Create row from each column and fill each row with each column

``````1) Create empty array
2) Create row for each column
3) Get each element from same column and insert into row
4) Return result``````

⚠️ Common Mistakes

• Not every 2D-Array problem follows the common techniques.

## 4: I-mplement

Implement the code to solve the algorithm.

Solution 1:

``````class Solution:
def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
# Use zip function on the unpacked matrix array, to gather the first elements together and form a group and so forth.
return zip(*matrix)``````

Solution 2:

``````class Solution:
def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
# Use list comprehesion to access the column, to gather elements in row by column
return [[matrix[i][j] for i in range(len(matrix))] for j in range(len(matrix))]``````

Solution 3:

``````class Solution:
def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
# Create empty array
result = []
# Create row for each column
for j in range(len(matrix)):
result.append([])
# Get each element from same column and insert into row
for i in range(len(matrix)):
result[j].append(matrix[i][j])
# Return result
return result``````
``````class Solution {
public int[][] transpose(int[][] A) {
//Create empty array
int M = A.length; int N = A.length;
int[][] B = new int[N][M];

// Create row for each column
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
// Get each element from same column and insert into row
B[j][i] = A[i][j];
}
}
// Return result
return B;
}
}``````

## 5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Trace through your code with an input to check for the expected output
• Catch possible edge cases and off-by-one errors

## 6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume `N` represents the number of rows in 2D-array. Assume `M` represents the number of columns in 2D-array.

All 3 solutions results in the same space and time complexity

• Time Complexity: O(N * M) we need to view each item in the 2D-Array
• Space Complexity: O(N * M), because we need space to hold the resulting matrix 