Transpose Matrix

▶

Steps

setup

Initialize matrix size

Calculate the size 'n' of the matrix, which is the number of rows (and columns).

💡 Knowing the matrix size is essential to control the loops that perform the transpose.

Line:

n = len(matrix)

💡 The matrix is square, so the number of rows equals the number of columns.

setup

Check for single element matrix

Check if the matrix size is 1, which means no transpose is needed.

💡 This early exit avoids unnecessary work for trivial cases.

Line:

if n == 1:
    return

💡 Since the matrix is larger than 1x1, the algorithm proceeds to transpose.

traverse

Start outer loop with i=0

Set pointer 'i' to 0, representing the first row to process swaps above the diagonal.

💡 The outer loop controls which row we are currently transposing elements for.

Line:

for i in range(n):

💡 We begin with the first row, where swaps will occur with columns greater than i.

traverse

Start inner loop with j=1

Set pointer 'j' to 1, the first column above the diagonal for row 0.

💡 The inner loop selects columns above the diagonal to swap with row i.

Line:

for j in range(i + 1, n):

💡 We will swap elements at (0,1) and (1,0).

swap

Swap elements at (0,1) and (1,0)

Swap the elements 2 and 4 to transpose the matrix in place.

💡 Swapping these elements flips the matrix over its diagonal for this pair.

Line:

matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

💡 Swapping elements above the diagonal with their symmetric counterparts below the diagonal is the core of transpose.

traverse

Move inner loop pointer j to 2

Increment 'j' to 2 to swap the next pair above the diagonal in row 0.

💡 We continue swapping elements in the first row with columns beyond the diagonal.

Line:

for j in range(i + 1, n):  # j=2

💡 Next pair to swap is (0,2) and (2,0).

swap

Swap elements at (0,2) and (2,0)

Swap the elements 3 and 7 to continue transposing the matrix.

💡 This swap moves the element from the first row to the first column and vice versa.

Line:

matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

💡 Each swap moves elements to their transposed positions without extra space.

traverse

Increment outer loop pointer i to 1

Move 'i' to 1 to start processing the second row for swaps above the diagonal.

💡 After finishing row 0, the algorithm moves to the next row.

Line:

for i in range(n):  # i=1

💡 Now swaps will occur for elements in row 1 with columns greater than 1.

traverse

Start inner loop with j=2 for i=1

Set 'j' to 2 to swap elements above the diagonal in row 1.

💡 Only one element above the diagonal remains in this row to swap.

Line:

for j in range(i + 1, n):  # j=2

💡 We will swap elements at (1,2) and (2,1).

swap

Swap elements at (1,2) and (2,1)

Swap the elements 6 and 8 to complete the transpose.

💡 This final swap places the last pair of elements in their transposed positions.

Line:

matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

💡 All elements above the diagonal have been swapped with their symmetric counterparts.

traverse

Increment outer loop pointer i to 2

Move 'i' to 2, the last row, where no swaps are needed above the diagonal.

💡 No columns exist above the diagonal for the last row, so no swaps occur.

Line:

for i in range(n):  # i=2

💡 The algorithm finishes after processing all rows.

reconstruct

Transpose complete

All swaps are done; the matrix is now transposed in-place.

💡 The matrix has been flipped over its diagonal without extra space.

Line:

return  # end of function

💡 The in-place transpose is efficient and modifies the original matrix.

def transpose(matrix):
    n = len(matrix)  # STEP 1
    if n == 1:       # STEP 2
        return
    for i in range(n):  # STEP 3, 8, 11
        for j in range(i + 1, n):  # STEP 4, 6, 9
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]  # STEP 5, 7, 10

📊

Transpose Matrix - Watch the Algorithm Execute, Step by Step

Watching each swap and pointer movement reveals how the matrix is flipped over its diagonal without extra space, making the transpose operation efficient and clear.

setup

0

1

2

compare

0

1

2

traverse

i

0

1

2

compare

i

0

j

1

2

swap

i

0

j

1

2

compare

i

0

1

j

2

swap

i

0

1

j

2

traverse

0

i

1

2

compare

0

i

1

j

2

swap

0

i

1

j

2

traverse

0

1

i

2

record

0

1

2

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

Key Takeaways

✓ The transpose is done in-place by swapping elements above the diagonal with their symmetric counterparts below.

This insight is hard to see from code alone because the swapping logic is compact; visualization shows exactly which elements move.

✓ The algorithm only processes elements above the diagonal, avoiding redundant swaps and ensuring efficiency.

Seeing the pointers 'i' and 'j' move clarifies why the inner loop starts at i+1, which might be confusing from code alone.

✓ The matrix gradually transforms after each swap, revealing the stepwise nature of the transpose operation.

Watching the matrix state after each swap helps understand how the final transposed matrix emerges.

Practice

1. Given the following code for maximum hourglass sum using sliding window, what is the value of max_sum after processing the first row (i=0) of the matrix below? Matrix: [[1, 1, 1, 0], [0, 1, 0, 0], [1, 1, 1, 0]]

def max_hourglass_sum_sliding(matrix):
    n = len(matrix)
    m = len(matrix[0])
    max_sum = float('-inf')

    for i in range(n - 2):
        current_sum = (matrix[i][0] + matrix[i][1] + matrix[i][2] +
                       matrix[i+1][1] +
                       matrix[i+2][0] + matrix[i+2][1] + matrix[i+2][2])
        if current_sum > max_sum:
            max_sum = current_sum

        for j in range(1, m - 2):
            current_sum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1])
            current_sum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2])
            if current_sum > max_sum:
                max_sum = current_sum
    return max_sum

easy

A. 7

B. 8

C. 6

D. 9

Solution

1. Step 1: Calculate initial hourglass sum at i=0, j=0

   Sum = 1+1+1 + 1 + 1+1+1 = 7

2. Step 2: Check sliding window for j=1 (only one possible)

   Subtract left column: 1 + 1 + 1 = 3; Add right column: 0 + 0 + 0 = 0; New sum = 7 - 3 + 0 = 4; max_sum remains 7

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Initial sum 7 is max after first row [OK]

Hint: Initial hourglass sum sets max before sliding [OK]

Common Mistakes:

• Off-by-one in sliding window update
• Forgetting to update max_sum after sliding
• Misindexing matrix elements

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. What is the time complexity of the optimal approach to compute the sum of the diagonals of an n x n matrix using a single loop that sums mat[i][i] and mat[i][n-1-i] for i in [0, n-1]?

medium

A. O(n) because the loop runs n times and each iteration does constant work

B. O(n^2) because we access two elements per iteration and n iterations

C. O(1) because only two elements are accessed per iteration

D. O(n log n) due to index calculations inside the loop

Solution

1. Step 1: Identify loop iterations

   The loop runs exactly n times, once for each row index i.

2. Step 2: Analyze work per iteration

   Each iteration accesses exactly two elements and performs constant time addition.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time O(n) matches single loop with constant work [OK]

Hint: Single loop with constant work per iteration is O(n) [OK]

Common Mistakes:

• Confusing element accesses with nested loops
• Assuming index calculations add log n factor
• Mistaking constant work for O(1) total

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 Sudoku validation problem is extended so that the board size is variable (N x N), where N is a perfect square (e.g., 4x4, 16x16), and digits range from 1 to N. Which of the following modifications to the bitmasking approach is necessary to correctly validate such boards?

hard

A. Use larger integer types or multiple integers to represent bitmasks since N can exceed 32 bits.

B. Keep the same 9x9 fixed-size arrays and bitmasks since the logic is identical regardless of N.

C. Replace bitmasking with hash sets because bitmasking only works for 9x9 boards.

D. Only check rows and columns; boxes are not needed for variable-sized boards.

Solution

1. Step 1: Understand bitmask size limitation

   Bitmasking uses bits to represent digits; for N > 32, a single integer is insufficient.

2. Step 2: Modify data structures accordingly

   Use larger integer types (e.g., 64-bit) or multiple integers/arrays to represent bitmasks for larger N.

3. Step 3: Confirm boxes must still be checked

   Boxes remain part of the constraints; logic must adapt to variable box sizes.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Bitmask size must scale with N to represent all digits [OK]

Hint: Bitmask size must scale with board size N [OK]

Common Mistakes:

• Assuming fixed 9x9 arrays suffice
• Dropping box checks
• Thinking bitmasking can't scale at all