Transpose Matrix

🎯

Transpose Matrix

easyMATRIXAmazonGoogle

Imagine you have a spreadsheet and want to flip its rows and columns to analyze data from a different perspective.

💡 Transposing a matrix means flipping it over its diagonal, turning rows into columns. Beginners often struggle because they confuse indices or try to create a new matrix instead of doing it in-place, which is more efficient.

📋

Problem Statement

Given an n x n 2D matrix, transpose the matrix in-place, i.e., convert all rows to columns and columns to rows without using extra space for another matrix.

1 ≤ n ≤ 300matrix[i][j] is an integer

💡

Example

Input"[[1,2,3],[4,5,6],[7,8,9]]"

Output[[1,4,7],[2,5,8],[3,6,9]]

The element at position (0,1) moves to (1,0), (0,2) to (2,0), and so forth, effectively flipping the matrix over its diagonal.

• 1x1 matrix → same matrix
• Matrix with all identical elements → same matrix after transpose
• Matrix with negative numbers → transpose preserves values correctly
• Matrix with zeros and positive numbers → transpose preserves zeros correctly

⚠️

Common Mistakes

Swapping elements twice by iterating over entire matrix

Matrix ends up unchanged or swapped back to original

✅ Only iterate over elements above the diagonal (j > i) to swap once

Trying to transpose non-square matrix in-place

Index out of range errors or incorrect results

✅ Check matrix dimensions and use extra space for non-square matrices

Not handling 1x1 matrix edge case

Unnecessary loops or confusion in code

✅ Add early return for single element matrix

Using extra space when in-place is required

Suboptimal solution rejected by interviewer

✅ Learn and implement in-place swapping approach

🧠

Brute Force (Using Extra Matrix)

💡 This approach helps beginners understand the transpose concept clearly by creating a new matrix instead of modifying in-place, which is simpler but uses extra space.

Intuition

Create a new matrix where each element at position (i, j) in the original matrix is placed at (j, i) in the new matrix.

Algorithm

1. Initialize a new n x n matrix.
2. Iterate over each element in the original matrix.
3. Assign the element at (i, j) in original to (j, i) in the new matrix.
4. Copy the new matrix back to the original matrix if needed.

💡 This step-by-step helps visualize the transpose operation clearly before tackling in-place complexity.

</>

Code

def transpose(matrix):
    n = len(matrix)
    transposed = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            transposed[j][i] = matrix[i][j]
    for i in range(n):
        for j in range(n):
            matrix[i][j] = transposed[i][j]

# Driver code
if __name__ == '__main__':
    mat = [[1,2,3],[4,5,6],[7,8,9]]
    transpose(mat)
    print(mat)

Line Notes

n = len(matrix)Determine the size of the square matrix to set loop bounds.

transposed = [[0]*n for _ in range(n)]Create a new matrix initialized with zeros to store the transpose.

for i in range(n):Outer loop iterates over rows of the original matrix.

transposed[j][i] = matrix[i][j]Assign element from original (i,j) to transposed (j,i), performing the transpose.

import java.util.Arrays;
public class Transpose {
    public static void transpose(int[][] matrix) {
        int n = matrix.length;
        int[][] transposed = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                transposed[j][i] = matrix[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = transposed[i][j];
            }
        }
    }
    public static void main(String[] args) {
        int[][] mat = {{1,2,3},{4,5,6},{7,8,9}};
        transpose(mat);
        System.out.println(Arrays.deepToString(mat));
    }
}

Line Notes

int n = matrix.length;Get the dimension of the square matrix for iteration limits.

int[][] transposed = new int[n][n];Create a new matrix to hold the transposed values.

transposed[j][i] = matrix[i][j];Swap row and column indices to transpose elements.

matrix[i][j] = transposed[i][j];Copy back the transposed matrix to the original matrix.

#include <iostream>
#include <vector>
using namespace std;

void transpose(vector<vector<int>>& matrix) {
    int n = matrix.size();
    vector<vector<int>> transposed(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            transposed[j][i] = matrix[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            matrix[i][j] = transposed[i][j];
        }
    }
}

int main() {
    vector<vector<int>> mat = {{1,2,3},{4,5,6},{7,8,9}};
    transpose(mat);
    for (auto& row : mat) {
        for (auto& val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

int n = matrix.size();Determine matrix size for loops.

vector<vector<int>> transposed(n, vector<int>(n, 0));Create a new matrix initialized with zeros for transpose.

transposed[j][i] = matrix[i][j];Assign transposed element by swapping indices.

matrix[i][j] = transposed[i][j];Overwrite original matrix with transposed values.

function transpose(matrix) {
    const n = matrix.length;
    const transposed = Array.from({length: n}, () => Array(n).fill(0));
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            transposed[j][i] = matrix[i][j];
        }
    }
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            matrix[i][j] = transposed[i][j];
        }
    }
}

// Test
const mat = [[1,2,3],[4,5,6],[7,8,9]];
transpose(mat);
console.log(mat);

Line Notes

const n = matrix.length;Get matrix dimension for iteration.

const transposed = Array.from({length: n}, () => Array(n).fill(0));Create new matrix filled with zeros for transpose.

transposed[j][i] = matrix[i][j];Swap indices to assign transposed elements.

matrix[i][j] = transposed[i][j];Copy transposed matrix back to original.

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

We visit each element twice: once to create the transposed matrix and once to copy back, and we use extra space equal to the matrix size.

💡 For n=3, this means about 18 operations and extra space for 9 elements, which is manageable but not optimal.

Interview Verdict: Accepted but not optimal due to extra space

This approach works but wastes memory; interviewers expect you to optimize space.

🧠

In-Place Transpose by Swapping Elements

💡 This approach is more efficient because it transposes the matrix without extra space by swapping elements across the diagonal.

Intuition

Only swap elements above the diagonal with their corresponding elements below the diagonal to avoid double swapping.

Algorithm

1. Iterate over rows from 0 to n-1.
2. For each row, iterate over columns from i+1 to n-1 to avoid redundant swaps.
3. Swap element at (i, j) with element at (j, i).
4. Continue until all elements above the diagonal are swapped.

💡 Skipping the diagonal and lower triangle prevents undoing swaps and reduces operations.

</>

Code

def transpose(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

# Driver code
if __name__ == '__main__':
    mat = [[1,2,3],[4,5,6],[7,8,9]]
    transpose(mat)
    print(mat)

Line Notes

n = len(matrix)Get matrix size for loop bounds.

for i in range(n):Outer loop iterates over rows.

for j in range(i + 1, n):Inner loop iterates only over columns above the diagonal to avoid double swaps.

matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]Swap elements symmetrically across the diagonal.

import java.util.Arrays;
public class Transpose {
    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[][] mat = {{1,2,3},{4,5,6},{7,8,9}};
        transpose(mat);
        System.out.println(Arrays.deepToString(mat));
    }
}

Line Notes

int n = matrix.length;Determine matrix size for iteration.

for (int i = 0; i < n; i++) {Outer loop over rows.

for (int j = i + 1; j < n; j++) {Inner loop over columns above diagonal to avoid redundant swaps.

int temp = matrix[i][j];Temporarily store element for swapping.

#include <iostream>
#include <vector>
using namespace std;

void transpose(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
}

int main() {
    vector<vector<int>> mat = {{1,2,3},{4,5,6},{7,8,9}};
    transpose(mat);
    for (auto& row : mat) {
        for (auto& val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

int n = matrix.size();Get matrix dimension for loops.

for (int i = 0; i < n; i++) {Outer loop iterates over rows.

for (int j = i + 1; j < n; j++) {Inner loop iterates over columns above diagonal.

swap(matrix[i][j], matrix[j][i]);Swap elements across the diagonal in-place.

function transpose(matrix) {
    const n = matrix.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }
}

// Test
const mat = [[1,2,3],[4,5,6],[7,8,9]];
transpose(mat);
console.log(mat);

Line Notes

const n = matrix.length;Get matrix size for iteration.

for (let i = 0; i < n; i++) {Outer loop over rows.

for (let j = i + 1; j < n; j++) {Inner loop over columns above diagonal to avoid double swaps.

[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];Swap elements in-place using destructuring assignment.

⏱

Complexity

TimeO(n^2)

SpaceO(1)

We only visit each element above the diagonal once and swap it, no extra space is used.

💡 For n=3, this means about 3 swaps and no extra memory, making it efficient.

Interview Verdict: Accepted and optimal for in-place transpose

This is the preferred approach in interviews because it uses no extra space and is easy to implement.

🧠

In-Place Transpose with Early Exit for Single Element Matrix

💡 This approach adds a quick check to handle the trivial case of a 1x1 matrix, avoiding unnecessary loops.

Intuition

If the matrix size is 1, no transpose is needed; otherwise, perform in-place swapping as before.

Algorithm

1. Check if matrix size is 1; if yes, return immediately.
2. Otherwise, iterate over rows and columns above the diagonal.
3. Swap elements at (i, j) and (j, i).
4. Finish after all swaps.

💡 This small optimization can save time in edge cases and shows attention to detail.

</>

Code

def transpose(matrix):
    n = len(matrix)
    if n == 1:
        return
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

# Driver code
if __name__ == '__main__':
    mat = [[1]]
    transpose(mat)
    print(mat)

Line Notes

n = len(matrix)Get matrix size for condition and loops.

if n == 1:Check for trivial 1x1 matrix to skip unnecessary work.

for i in range(n):Outer loop over rows for swapping.

matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]Swap elements across diagonal in-place.

import java.util.Arrays;
public class Transpose {
    public static void transpose(int[][] matrix) {
        int n = matrix.length;
        if (n == 1) return;
        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[][] mat = {{1}};
        transpose(mat);
        System.out.println(Arrays.deepToString(mat));
    }
}

Line Notes

int n = matrix.length;Get matrix size for condition and loops.

if (n == 1) return;Early exit for trivial 1x1 matrix.

for (int i = 0; i < n; i++) {Outer loop over rows.

int temp = matrix[i][j];Temporary variable for swapping elements.

#include <iostream>
#include <vector>
using namespace std;

void transpose(vector<vector<int>>& matrix) {
    int n = matrix.size();
    if (n == 1) return;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
}

int main() {
    vector<vector<int>> mat = {{1}};
    transpose(mat);
    for (auto& row : mat) {
        for (auto& val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

int n = matrix.size();Get matrix size for condition and loops.

if (n == 1) return;Skip transpose for single element matrix.

for (int i = 0; i < n; i++) {Outer loop over rows.

swap(matrix[i][j], matrix[j][i]);Swap elements across diagonal in-place.

function transpose(matrix) {
    const n = matrix.length;
    if (n === 1) return;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }
}

// Test
const mat = [[1]];
transpose(mat);
console.log(mat);

Line Notes

const n = matrix.length;Get matrix size for condition and loops.

if (n === 1) return;Early return for trivial case.

for (let i = 0; i < n; i++) {Outer loop over rows.

[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];Swap elements in-place using destructuring.

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Same as previous approach but with an early exit for trivial cases.

💡 For n=1, this saves time by skipping loops entirely.

Interview Verdict: Accepted and optimal with minor optimization

This small optimization shows attention to detail and can be mentioned in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, coding the in-place swapping approach is best because it is optimal and straightforward.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Extra Matrix)	O(n^2)	O(n^2)	No	N/A	Mention only - never code
2. In-Place Swapping	O(n^2)	O(1)	No	N/A	Code this approach
3. In-Place with Early Exit	O(n^2) but faster for n=1	O(1)	No	N/A	Mention as minor optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and learn how to communicate your thought process clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach using extra space to demonstrate understanding.Step 3: Optimize to in-place swapping to save space.Step 4: Mention edge cases and minor optimizations like early exit for 1x1 matrix.Step 5: Write clean, readable code and test with sample inputs.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 5min → Test: 5min. Total ~15min

What the Interviewer Tests

The interviewer tests your understanding of matrix indexing, ability to optimize space, and attention to edge cases.

Common Follow-ups

• How would you transpose a non-square matrix? → Explain that in-place transpose is not possible for non-square matrices; you need extra space.
• Can you rotate the matrix 90 degrees in-place? → Discuss the relation between transpose and reversing rows or columns.

💡 These follow-ups test your ability to generalize and connect related matrix transformations.

🔍

Pattern Recognition

When to Use

1) Problem involves flipping rows and columns, 2) Matrix is square, 3) In-place transformation is required, 4) Swapping symmetric elements is possible

Signature Phrases

transpose the matrixflip rows and columnsin-place transformation

NOT This Pattern When

Matrix multiplication or pathfinding in matrices are different patterns.

Similar Problems

Rotate Image - uses transpose plus row reversalSet Matrix Zeroes - involves matrix manipulation and indexingSpiral Matrix - involves matrix traversal patterns

Practice

1. You are given a matrix of integers. You need to find all elements that are the smallest in their row and simultaneously the largest in their column. Which approach guarantees an optimal solution to this problem?

easy

A. Use a brute force approach checking each element by scanning its entire row and column repeatedly.

B. Precompute the minimum value of each row and the maximum value of each column, then find elements matching both conditions in a single pass.

C. Apply a dynamic programming approach to store intermediate minimum and maximum values for submatrices.

D. Use a greedy approach by selecting the smallest element in each row and checking if it is the largest in its column.

Solution

1. Step 1: Understand problem constraints

   The problem requires identifying elements that are simultaneously the minimum in their row and maximum in their column.

2. Step 2: Evaluate approaches

   Brute force (A) is correct but inefficient. DP (C) is unnecessary overhead. Greedy (D) can fail if multiple minimums exist in a row but only one is maximum in its column. Precomputing row minimums and column maximums (B) allows a single pass to find all lucky numbers efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Precompute arrays then single pass -> optimal and correct [OK]

Hint: Precompute mins and maxes for single pass [OK]

Common Mistakes:

• Assuming greedy selection per row suffices
• Using DP unnecessarily
• Brute force is too slow

2. Consider the following Python code for finding lucky numbers in a matrix:

from typing import List

def luckyNumbers(matrix: List[List[int]]) -> List[int]:
    m, n = len(matrix), len(matrix[0])
    row_mins = [min(row) for row in matrix]
    col_maxs = [max(matrix[i][j] for i in range(m)) for j in range(n)]
    return [matrix[i][j] for i in range(m) for j in range(n) if matrix[i][j] == row_mins[i] == col_maxs[j]]

mat = [[3,7,8],[9,11,13],[15,16,17]]
print(luckyNumbers(mat))

What is the output of this code?

easy

A. [15]

B. [3, 11, 17]

C. [8, 13, 17]

D. [7, 11, 16]

Solution

1. Step 1: Compute row minimums

   Row 0 min = 3, Row 1 min = 9, Row 2 min = 15.

2. Step 2: Compute column maximums

   Col 0 max = max(3,9,15) = 15, Col 1 max = max(7,11,16) = 16, Col 2 max = max(8,13,17) = 17.

3. Step 3: Find elements equal to both row min and column max

   Check each element: - (2,0) = 15 equals row 2 min and col 0 max -> lucky number. No other elements satisfy both conditions.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Only 15 matches both conditions -> output [15] [OK]

Hint: Check row mins and col maxs carefully [OK]

Common Mistakes:

• Confusing min and max
• Off-by-one indexing
• Returning all row mins or col maxs

3. Suppose you want to extend diagonal traversal to handle matrices where elements can be updated dynamically and you need to output the diagonal traversal multiple times efficiently. Which modification to the algorithm is most appropriate?

hard

A. Precompute and store all diagonals in separate lists to allow O(1) retrieval per traversal.

B. Use the original traversal code each time since it is already optimal with O(m*n) time.

C. Flatten the matrix into a 1D array and sort it to simulate diagonal traversal.

D. Maintain a segment tree per diagonal to support dynamic updates and queries efficiently.

Solution

1. Step 1: Understand the requirement for dynamic updates

   Repeated diagonal traversals with updates require efficient update and query support.

2. Step 2: Evaluate options for dynamic support

   Precomputing diagonals (A) is fast for static data but inefficient for updates. Original code (B) recomputes fully each time. Flattening and sorting (D) loses diagonal order and is inefficient.

3. Step 3: Use segment trees per diagonal

   Segment trees allow efficient updates and queries on each diagonal, enabling fast repeated traversals.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Segment trees balance update and query efficiency for dynamic diagonal traversal [OK]

Hint: Dynamic updates require data structures supporting fast queries [OK]

Common Mistakes:

• Assuming original code is always optimal for dynamic queries

4. Suppose the problem is modified so that instead of zeroing rows and columns, you must zero only the rows and columns of the first zero found (in row-major order). Which modification to the optimal in-place algorithm correctly implements this variant?

hard

A. Use sets to track all zero positions but only apply zeroing to the first zero's row and column after scanning.

B. Use the original algorithm but stop marking after the first zero is found, then zero rows and columns accordingly.

C. Scan the matrix once to find the first zero, then zero its entire row and column directly without using flags.

D. Modify the flagging approach to mark only the first zero's row and column, ignoring others.

Solution

1. Step 1: Understand the variant

   Only the first zero's row and column should be zeroed, so no need to track multiple zeros.

2. Step 2: Choose direct zeroing

   Scanning once to find the first zero, then zeroing its row and column directly is simplest and correct.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Direct zeroing after first zero found matches problem variant [OK]

Hint: Stop at first zero, zero its row and column directly [OK]

Common Mistakes:

• Continuing to mark all zeros wastes time and zeroes extra rows/columns
• Trying to adapt flagging for only one zero complicates logic unnecessarily
• Using sets but applying zeroing to all zeros instead of just first

5. Suppose you want to output the spiral order of a matrix but now the matrix can contain negative numbers and zero, and you want to skip all zeros during traversal. Which modification to the optimal boundary shrinking algorithm correctly handles this variant without revisiting elements or breaking order?

hard

A. Add a visited matrix to mark skipped zeros and continue traversal using direction vectors.

B. Modify the boundary shrinking algorithm to skip zeros during appending but still shrink boundaries normally.

C. Use a brute force nested loop with boundary checks and skip zeros when appending elements.

D. Traverse the matrix in spiral order but collect only non-zero elements, ignoring zeros without changing traversal.

Solution

1. Step 1: Understand the challenge of skipping zeros

   Skipping zeros means some elements are not appended, but traversal must still visit all cells exactly once without repeats.

2. Step 2: Why boundary shrinking alone fails

   Boundary shrinking assumes all elements are appended; skipping zeros breaks this assumption causing incorrect boundaries or missed elements.

3. Step 3: Using a visited matrix with direction vectors

   Tracking visited cells allows skipping zeros safely while continuing traversal correctly without revisiting or missing elements.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Visited matrix ensures correct traversal despite skipping zeros [OK]

Hint: Skipping elements breaks boundary assumptions; track visited cells [OK]

Common Mistakes:

• Skipping zeros but shrinking boundaries as usual causing missed elements
• Ignoring visited tracking leading to infinite loops or repeats
• Using brute force which is inefficient