Transpose Matrix

📋

Problem

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

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

Edge cases: 1x1 matrix → same matrixMatrix with all identical elements → same matrix after transposeMatrix with negative numbers → transpose preserves values correctly

</>

IDE

def transpose(matrix: list[list[int]]) -> None:public void transpose(int[][] matrix)void transpose(vector<vector<int>>& matrix)function transpose(matrix)

def transpose(matrix):
    # Write your solution here
    pass

class Solution {
    public void transpose(int[][] matrix) {
        // Write your solution here
    }
}

#include <vector>
using namespace std;

void transpose(vector<vector<int>>& matrix) {
    // Write your solution here
}

function transpose(matrix) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[1,2,3],[4,5,6],[7,8,9]]No swaps performed; code returns original matrix unchanged.✅ Add nested loops to swap matrix[i][j] and matrix[j][i] for j > i.

Wrong: [[1,4,7],[4,5,6],[7,8,9]]Partial swaps only on first row or column, missing others.✅ Ensure inner loop j starts from i+1 and covers all pairs.

Wrong: [[1,4,7],[2,5,8],[3,6,9]]Returns new matrix instead of modifying input in-place.✅ Modify input matrix by swapping elements in-place without creating new matrix.

Wrong: [[1,4,7],[2,5,8],[3,6,0]]Incorrect swap logic causing last element to be zero or wrong value.✅ Use a temporary variable to swap matrix[i][j] and matrix[j][i] safely.

✓

Test Cases

Try testing your code on the smallest matrices and those with identical elements.

Consider common mistakes like off-by-one errors and confusing in-place with extra space.

Focus on algorithmic complexity and avoid nested loops with unnecessary overhead.

t1_01basic

Input{"matrix":[[1,2,3],[4,5,6],[7,8,9]]}

Expectednull

⏱ Performance - must finish in 2000ms

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.

💡 Think about swapping elements across the main diagonal.

💡 Use nested loops where j starts from i+1 to avoid double swapping.

💡 Swap matrix[i][j] with matrix[j][i] only when j > i.

Why it failed: Failed to swap elements symmetrically across diagonal or swapped all pairs twice causing incorrect final matrix. Fix by swapping only when j > i.

✓ Matrix correctly transposed in-place by swapping elements across the diagonal.

t1_02basic

Input{"matrix":[[1,2],[3,4]]}

Expectednull

⏱ Performance - must finish in 2000ms

Swapping elements (0,1) and (1,0) transposes the 2x2 matrix.

💡 Transpose swaps elements across the diagonal.

💡 For 2x2 matrix, swap matrix[0][1] and matrix[1][0].

💡 Ensure no extra matrix is used and swap in-place.

Why it failed: Incorrect output due to missing or extra swaps; ensure swapping only once per pair and no extra space used.

✓ Correct in-place transpose for 2x2 matrix.

t2_01edge

Input{"matrix":[[42]]}

Expectednull

⏱ Performance - must finish in 2000ms

1x1 matrix remains the same after transpose.

💡 Check behavior when matrix size is 1.

💡 No swaps needed for single element matrix.

💡 Return matrix as is without modification.

Why it failed: Code attempts swaps on single element matrix causing errors or changes; add condition to skip swaps if n=1.

✓ Correctly handles 1x1 matrix with no changes.

t2_02edge

Input{"matrix":[[7,7,7],[7,7,7],[7,7,7]]}

Expectednull

⏱ Performance - must finish in 2000ms

Matrix with all identical elements remains unchanged after transpose.

💡 Transpose should not alter values, only positions.

💡 Check that swapping identical elements does not cause errors.

💡 Ensure swapping logic works even if values are the same.

Why it failed: Fails when swapping identical elements due to incorrect indexing or overwriting; fix swap indices and use temp variable.

✓ Correctly transposes matrix with identical elements without error.

t2_03edge

Input{"matrix":[[-1,0],[100,-100]]}

Expectednull

⏱ Performance - must finish in 2000ms

Transpose preserves negative and zero values correctly.

💡 Values can be negative or zero; swapping should not affect values.

💡 Check that no arithmetic operations alter values during swap.

💡 Use a temporary variable to swap values safely.

Why it failed: Incorrect output due to arithmetic swap causing value corruption; fix by using a temporary variable for swapping.

✓ Correctly transposes matrix preserving negative and zero values.

t3_01corner

Input{"matrix":[[1,2,3],[4,5,6],[7,8,9]]}

Expectednull

⏱ Performance - must finish in 2000ms

Checks for off-by-one error in loops causing incomplete or extra swaps.

💡 Verify loop boundaries carefully for i and j.

💡 j should start from i+1 to avoid double swapping or missing swaps.

💡 Fix loop to for i in range(n), for j in range(i+1, n).

Why it failed: Off-by-one error in inner loop causes missing or double swaps; fix loop to start j from i+1.

✓ Loops correctly iterate to swap all required pairs exactly once.

t3_02corner

Input{"matrix":[[1,2],[3,4]]}

Expectednull

⏱ Performance - must finish in 2000ms

Detects confusion between in-place transpose and creating a new matrix.

💡 In-place transpose requires swapping elements, not creating new matrix.

💡 Avoid allocating extra space for transposed matrix.

💡 Fix by swapping matrix[i][j] and matrix[j][i] in-place.

Why it failed: Incorrect output due to returning or using a new matrix instead of modifying input in-place; fix by swapping elements in original matrix.

✓ In-place transpose correctly modifies input matrix without extra space.

t3_03corner

Input{"matrix":[[1,2,3],[4,5,6],[7,8,9]]}

Expectednull

⏱ Performance - must finish in 2000ms

Catches greedy approach that tries to swap only some elements, missing others.

💡 Greedy approach might swap only first row or column.

💡 Transpose requires swapping all pairs above diagonal.

💡 Fix by nested loops with j starting at i+1 to cover all pairs.

Why it failed: Partial swapping leads to incorrect transpose; fix by swapping all pairs (i,j) with j>i.

✓ All required pairs swapped, full transpose achieved.

t4_01performance

Input{"_description":"n=300 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

n=300, O(n^2) algorithm must complete within 2 seconds.

💡 Transpose requires O(n^2) swaps.

💡 Avoid nested loops with unnecessary overhead.

💡 Use efficient in-place swapping without extra memory.

Why it failed: TLE due to O(n^3) or inefficient approach; fix by using O(n^2) in-place swapping loops.

✓ Algorithm runs in O(n^2) time and completes within time limit.

Practice

1. You are given a 2D matrix and need to output its elements in a zigzag pattern that moves along the diagonals, alternating direction each diagonal. Which algorithmic approach best guarantees an optimal solution for this traversal?

easy

A. Simulate diagonal traversal by iterating over each diagonal and alternating direction for each diagonal.

B. Use a greedy approach that picks the next element based on local maximum value.

C. Apply dynamic programming to store intermediate sums along diagonals.

D. Perform a breadth-first search (BFS) starting from the top-left corner.

Solution

1. Step 1: Understand the traversal pattern

   The problem requires visiting elements along diagonals, alternating direction each diagonal, which matches a diagonal traversal pattern.

2. Step 2: Identify the approach that matches this pattern

   Simulating traversal by iterating over each diagonal and alternating direction ensures all elements are visited in the required order efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Diagonal iteration with direction flip matches problem requirements [OK]

Hint: Diagonal traversal alternates direction per diagonal [OK]

Common Mistakes:

• Confusing with BFS or DP which don't fit traversal order

2. Consider the following Python code snippet for validating a Sudoku board using bitmasking:

def isValidSudoku(board):
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9
    for i in range(9):
        for j in range(9):
            if board[i][j] == '.':
                continue
            val = ord(board[i][j]) - ord('1')
            mask = 1 << val
            box_index = (i // 3) * 3 + (j // 3)
            if (rows[i] & mask) or (cols[j] & mask) or (boxes[box_index] & mask):
                return false
            rows[i] |= mask
            cols[j] |= mask
            boxes[box_index] |= mask
    return true

board = [
    ['5','3','.','.','7','.','.','.','.'],
    ['6','.','.','1','9','5','.','.','.'],
    ['.','9','8','.','.','.','.','6','.'],
    ['8','.','.','.','6','.','.','.','3'],
    ['4','.','.','8','.','3','.','.','1'],
    ['7','.','.','.','2','.','.','.','6'],
    ['.','6','.','.','.','.','2','8','.'],
    ['.','.','.','4','1','9','.','.','5'],
    ['.','.','.','.','8','.','.','7','9']
]

print(isValidSudoku(board))

What is the output of this code?

easy

A. true

B. false

C. Raises an exception due to invalid indexing

D. Returns null

Solution

1. Step 1: Trace first few iterations

   All digits are unique in their rows, columns, and boxes; no mask conflicts occur.

2. Step 2: Confirm no duplicates found

   Since no duplicates are detected, the function completes and returns true.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Standard valid Sudoku board returns true [OK]

Hint: No duplicates -> function returns true [OK]

Common Mistakes:

• Misreading box index calculation
• Assuming '.' causes errors
• Confusing return values

3. Examine the following buggy code snippet for Sudoku validation using bitmasking:

def isValidSudoku(board):
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9
    for i in range(9):
        for j in range(9):
            if board[i][j] == '.':
                continue
            val = ord(board[i][j]) - ord('1')
            mask = 1 << val
            box_index = i // 3 + (j // 3) * 3
            if (rows[i] & mask) or (cols[j] & mask) or (boxes[box_index] & mask):
                return false
            rows[i] |= mask
            cols[j] |= mask
            boxes[box_index] |= mask
    return true

What is the bug in this code?

medium

A. The rows and cols arrays should be initialized with sets, not integers.

B. The mask calculation is wrong; it should be 1 << (val + 1).

C. The code incorrectly includes '.' in the bitmask checks.

D. The box_index calculation is incorrect; it should be (i // 3) * 3 + (j // 3).

Solution

1. Step 1: Analyze box_index calculation

   The code uses box_index = i // 3 + (j // 3) * 3, which swaps row and column grouping.

2. Step 2: Correct formula for box_index

   The correct formula is (i // 3) * 3 + (j // 3) to map 3x3 boxes properly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Incorrect box_index causes missed duplicates in boxes [OK]

Hint: Box index formula must map 3x3 boxes correctly [OK]

Common Mistakes:

• Swapping row and column in box index
• Misusing bitmask shifts
• Including '.' in checks

4. Suppose the problem is modified so that the matrix is rectangular (not necessarily square). Which of the following statements about adapting the in-place rotation algorithm is true?

hard

A. The layer-by-layer four-way swap algorithm works unchanged for rectangular matrices.

B. In-place rotation is impossible for non-square matrices; extra space or a different approach is required.

C. Transposing and reversing rows can rotate rectangular matrices in-place without issues.

D. Rotating rectangular matrices by 90 degrees clockwise can be done by swapping elements only in the first row.

Solution

1. Step 1: Understand matrix shape constraints

   In-place rotation by 90 degrees requires the matrix to be square because dimensions swap (rows become columns).

2. Step 2: Evaluate options

   Layer-by-layer swaps rely on equal row and column counts; rectangular matrices require extra space or new matrix to hold rotated result.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Non-square matrices cannot be rotated in-place without dimension mismatch [OK]

Hint: In-place 90° rotation requires square matrix due to dimension swap [OK]

Common Mistakes:

• Assuming in-place rotation works for rectangular matrices
• Confusing transpose with rotation for non-square matrices

5. 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