Matrix Transpose
Java coding interview problem for Matrix Problems: Matrix Transpose.
Matrix manipulation is one of the most important topics in Data Structures and Algorithms.
The Matrix Transpose problem teaches fundamental concepts:
- Two-dimensional arrays
- Row and column transformation
- Index manipulation
- In-place operations
- Matrix rotation patterns
This concept is widely used in:
- Image processing
- Machine learning
- Data analytics
- Graphics programming
- Mathematical computations
What is Matrix Transpose?
The transpose of a matrix is obtained by converting:
Rows → Columns
Columns → Rows
In other words:
The element at position [i][j]
moves to
position [j][i]
Example 1
Original Matrix:
1 2 3
4 5 6
7 8 9
Transpose:
1 4 7
2 5 8
3 6 9
Position Transformation
Before:
matrix[i][j]
After transpose:
matrix[j][i]
Example:
Original:
matrix[0][1] = 2
After transpose:
matrix[1][0] = 2
Understanding Matrix Representation
A matrix is represented using a 2D array.
Example:
int[][] matrix = {
{1,2,3},
{4,5,6},
{7,8,9}
};
Representation:
Row 0:
1 2 3
Row 1:
4 5 6
Row 2:
7 8 9
Matrix Dimensions
A matrix has:
Rows × Columns
Example:
3 × 3 Matrix
means:
3 rows
3 columns
Rectangular Matrix Example
Input:
1 2 3
4 5 6
Dimensions:
2 × 3
Transpose:
1 4
2 5
3 6
Dimensions become:
3 × 2
Why Is Matrix Transpose Asked in Interviews?
Interviewers use this problem to test:
1. Index Understanding
Can you correctly map:
row → column
2. 2D Array Traversal
Can you iterate through:
matrix[i][j]
efficiently?
3. Space Optimization
Can you perform transformation:
without extra memory
?
4. Problem Pattern Recognition
Transpose is the base concept for:
- Rotate Image
- Matrix Reflection
- Grid Transformations
Real-World Applications
Image Processing
Images are represented as matrices.
Example:
Pixel Matrix
Transpose changes:
Height ↔ Width
Machine Learning
Data is often stored as:
Rows = Samples
Columns = Features
Transpose converts:
Feature Matrix
for mathematical operations.
Linear Algebra
Matrix operations require transpose for:
- Matrix multiplication
- Covariance calculation
- Optimization algorithms
Computer Graphics
Used for:
- Rotation
- Reflection
- Coordinate transformation
Problem Statement
Given a matrix:
matrix
return its transpose.
For every element:
matrix[i][j]
place it at:
transpose[j][i]
Example
Input:
[
[1,2,3],
[4,5,6],
[7,8,9]
]
Output:
[
[1,4,7],
[2,5,8],
[3,6,9]
]
Constraints
Example:
1 <= rows <= 1000
1 <= columns <= 1000
Values:
-10^9 <= matrix[i][j] <= 10^9
Matrix Visualization
Original:
Column
0 1 2
Row 0 1 2 3
Row 1 4 5 6
Row 2 7 8 9
Transpose:
Column
0 1 2
Row 0 1 4 7
Row 1 2 5 8
Row 2 3 6 9
Transpose Mathematical Concept
For a matrix:
A
Transpose is represented as:
Aᵀ
The rule:
Aᵀ[i][j] = A[j][i]
Dry Run Example
Input:
[
[1,2,3],
[4,5,6]
]
Dimensions:
2 × 3
Create result:
3 × 2
Process:
Element 1
Position:
[0][0]
Move to:
[0][0]
Result:
1
Element 2
Position:
[0][1]
Move to:
[1][0]
Result:
2
Element 3
Position:
[0][2]
Move to:
[2][0]
Result:
3
Element 4
Position:
[1][0]
Move to:
[0][1]
Result:
4
Final:
1 4
2 5
3 6
Approach 1 — Using Extra Matrix
The easiest approach is creating a new matrix.
Algorithm
Given:
rows = matrix.length
columns = matrix[0].length
Create:
columns × rows
matrix.
Copy:
result[j][i] = matrix[i][j]
Java Program
import java.util.Arrays;
public class MatrixTranspose {
public static int[][] transpose(
int[][] matrix) {
int rows =
matrix.length;
int columns =
matrix[0].length;
int[][] result =
new int[columns][rows];
for (int i = 0;
i < rows;
i++) {
for (int j = 0;
j < columns;
j++) {
result[j][i] =
matrix[i][j];
}
}
return result;
}
public static void main(String[] args) {
int[][] matrix =
{
{1,2,3},
{4,5,6}
};
int[][] result =
transpose(matrix);
for (int[] row : result) {
System.out.println(
Arrays.toString(row));
}
}
}
Output
[1, 4]
[2, 5]
[3, 6]
Step-by-Step Explanation
Input:
1 2 3
4 5 6
Create result:
3 × 2
Empty:
0 0
0 0
0 0
Copy:
matrix[0][0]
→ result[0][0]
Value:
1
Copy:
matrix[0][1]
→ result[1][0]
Value:
2
Copy:
matrix[1][2]
→ result[2][1]
Value:
6
Final:
1 4
2 5
3 6
Complexity Analysis
For a matrix:
rows × columns
we visit every element once.
Time:
O(rows × columns)
Space:
O(rows × columns)
because a new matrix is created.
Advantages
- Simple implementation.
- Works for all matrices.
- Easy to understand.
- Does not modify original matrix.
Drawbacks
- Requires extra memory.
- Not optimal for square matrices.
Approach 2 — In-Place Transpose for Square Matrix
For square matrices:
rows == columns
we can transpose without creating another matrix.
Example:
3 × 3
matrix.
Key Idea
Swap:
matrix[i][j]
with
matrix[j][i]
Only process:
j > i
to avoid swapping twice.
Example
Before:
1 2 3
4 5 6
7 8 9
Swap:
2 ↔ 4
3 ↔ 7
6 ↔ 8
After:
1 4 7
2 5 8
3 6 9
Java Program
public class MatrixTransposeInPlace {
public static void transpose(
int[][] matrix) {
int n =
matrix.length;
for (int i = 0;
i < n;
i++) {
for (int j = i + 1;
j < n;
j++) {
int temp =
matrix[i][j];
matrix[i][j] =
matrix[j][i];
matrix[j][i] =
temp;
}
}
}
public static void main(String[] args) {
int[][] matrix =
{
{1,2,3},
{4,5,6},
{7,8,9}
};
transpose(matrix);
for (int[] row : matrix) {
for (int value : row) {
System.out.print(
value + " ");
}
System.out.println();
}
}
}
Output
1 4 7
2 5 8
3 6 9
Complexity Analysis
Time:
O(n²)
Space:
O(1)
Advantages
- No extra matrix.
- Memory efficient.
- Best for square matrices.
Drawbacks
- Works only for square matrices.
- Modifies original matrix.
Transpose of Rectangular Matrix
The in-place transpose technique works only for:
Square Matrix
Example:
3 × 3
4 × 4
But many real-world matrices are rectangular.
Example:
2 × 3 Matrix
Input:
1 2 3
4 5 6
Transpose:
1 4
2 5
3 6
Dimensions change:
Before:
Rows = 2
Columns = 3
After transpose:
Rows = 3
Columns = 2
Why Can't We Transpose Rectangular Matrix In-Place?
Consider:
2 × 3
Matrix:
1 2 3
4 5 6
Memory layout:
1 2 3 4 5 6
After transpose:
1 4
2 5
3 6
Memory arrangement changes.
The original array size is:
2 × 3 = 6 elements
The new shape:
3 × 2
requires a different row-column structure.
Therefore:
Extra matrix is required.
Matrix Rotation Using Transpose
Matrix transpose is a building block for rotating images.
A very common interview problem:
Rotate a matrix 90 degrees clockwise.
Example
Input:
1 2 3
4 5 6
7 8 9
Step 1:
Transpose:
1 4 7
2 5 8
3 6 9
Step 2:
Reverse every row:
7 4 1
8 5 2
9 6 3
Final:
90 Degree Clockwise Rotation
90 Degree Rotation Algorithm
Steps:
- Transpose matrix.
- Reverse each row.
Java Program
public class RotateMatrix90 {
public static void rotate(
int[][] matrix) {
int n =
matrix.length;
// Step 1: Transpose
for (int i = 0;
i < n;
i++) {
for (int j = i + 1;
j < n;
j++) {
int temp =
matrix[i][j];
matrix[i][j] =
matrix[j][i];
matrix[j][i] =
temp;
}
}
// Step 2: Reverse rows
for (int i = 0;
i < n;
i++) {
int left = 0;
int right = n - 1;
while (left < right) {
int temp =
matrix[i][left];
matrix[i][left] =
matrix[i][right];
matrix[i][right] =
temp;
left++;
right--;
}
}
}
public static void main(String[] args) {
int[][] matrix =
{
{1,2,3},
{4,5,6},
{7,8,9}
};
rotate(matrix);
for (int[] row : matrix) {
for (int value : row) {
System.out.print(
value + " ");
}
System.out.println();
}
}
}
Output
7 4 1
8 5 2
9 6 3
Complexity Analysis
Time:
O(n²)
Space:
O(1)
Java Streams Approach
Matrix operations are usually not a good fit for Streams.
Reason:
A matrix requires:
- Index tracking
- Row-column transformation
- Mutation
Traditional loops are clearer.
Stream-Based Transpose Example
Using streams:
import java.util.Arrays;
public class MatrixTransposeStreams {
public static int[][] transpose(
int[][] matrix) {
int rows =
matrix.length;
int cols =
matrix[0].length;
return java.util.stream
.IntStream.range(0, cols)
.mapToObj(
col ->
java.util.stream
.IntStream.range(0, rows)
.map(row ->
matrix[row][col])
.toArray()
)
.toArray(int[][]::new);
}
}
Complexity Analysis
Time:
O(rows × columns)
Space:
O(rows × columns)
Why Traditional Loops Are Preferred?
For matrix problems:
Loops provide:
- Better readability
- Better performance
- Easier debugging
- Clear index mapping
Interviewers usually expect:
for loops
Comparison of All Approaches
| Approach | Matrix Type | Time Complexity | Space Complexity | Recommended |
|---|---|---|---|---|
| Extra Matrix | Any Matrix | O(rows × cols) | O(rows × cols) | Yes |
| In-place Swap | Square Only | O(n²) | O(1) | Best for square |
| Streams | Any Matrix | O(rows × cols) | O(rows × cols) | Learning only |
| Transpose + Reverse | Square Only | O(n²) | O(1) | Rotation problems |
Primitive vs Object Arrays
Primitive Matrix
Example:
int[][]
Advantages:
- Faster access
- Less memory
- No boxing overhead
Recommended for:
- Competitive programming
- Large matrices
Object Matrix
Example:
Integer[][]
Advantages:
- Works with Collections
- Supports null values
Disadvantages:
- Higher memory usage
Common Interview Mistakes
Mistake 1
Swapping all elements.
Wrong:
for(i=0;i<n;i++)
for(j=0;j<n;j++)
This swaps elements twice.
Mistake 2
Forgetting:
j = i + 1
For in-place transpose.
Correct:
for(int j=i+1;j<n;j++)
Mistake 3
Using in-place approach for rectangular matrices.
Incorrect:
2 × 3
matrix.
Mistake 4
Confusing transpose with rotation.
Transpose:
Rows ↔ Columns
Rotation:
Transpose + Reverse
Edge Cases
Empty Matrix
Input:
[]
Handle:
if(matrix.length == 0)
Single Element Matrix
Input:
[5]
Output:
[5]
Single Row Matrix
Input:
1 2 3
Transpose:
1
2
3
Single Column Matrix
Input:
1
2
3
Transpose:
1 2 3
Interview Follow-up Questions
Q1. Transpose a matrix.
Q2. Rotate matrix 90 degrees clockwise.
Q3. Rotate matrix 90 degrees anti-clockwise.
Q4. Rotate matrix by 180 degrees.
Q5. Perform transpose without extra space.
Q6. Transpose rectangular matrix.
Q7. Find diagonal elements.
Q8. Spiral traversal of matrix.
Related Problems
- Rotate Image
- Spiral Matrix
- Matrix Diagonal Traversal
- Set Matrix Zeroes
- Search a 2D Matrix
- Flood Fill Algorithm
- Number of Islands
Key Takeaways
Matrix transpose is a fundamental matrix transformation.
Core rule:
matrix[i][j]
becomes
matrix[j][i]
Approach selection:
Square Matrix?
|
Yes
|
In-place transpose
Rectangular Matrix?
|
Yes
|
Create new matrix
Frequently Asked Interview Questions
Q1. What is matrix transpose?
Changing rows into columns and columns into rows.
Q2. What is the formula?
Transpose[i][j] = Matrix[j][i]
Q3. Can transpose be done in-place?
Yes, only for square matrices.
Q4. How is transpose used in rotation?
90-degree rotation:
Transpose
+
Reverse rows
Q5. What is the complexity?
For matrix:
O(rows × columns)
Interview Tip
When asked:
"Transpose a matrix."
First identify:
- Is it square?
- Do we need to modify the original?
- Is extra memory allowed?
Then choose:
Square Matrix:
In-place swap
Rectangular Matrix:
Create result matrix
Understanding transpose deeply helps solve many advanced matrix problems.