Matrix Diagonal Sum

▶

Steps

setup

Initialize total and determine matrix size

Initialize the total sum to 0 and determine the size n of the matrix (3 in this case).

💡 Setting up total and n is essential to control the loop and accumulate the sum.

Line:

total = 0
n = len(mat)

💡 We know how many iterations to perform and have a variable ready to accumulate sums.

traverse

Start loop: i = 0, select primary diagonal element

At row 0, select the primary diagonal element mat[0][0] which is 1.

💡 Accessing the primary diagonal element is the first part of the sum for this row.

Line:

for i in range(n):
    total += mat[i][i]

💡 Primary diagonal elements have equal row and column indices.

insert

Add primary diagonal element to total

Add mat[0][0] = 1 to total. Total becomes 1.

💡 Adding the primary diagonal element contributes to the diagonal sum.

Line:

total += mat[i][i]

💡 The total accumulates the sum of diagonal elements as we iterate.

traverse

Select secondary diagonal element at row 0

At row 0, select the secondary diagonal element mat[0][2] which is 3.

💡 Secondary diagonal elements have column index n-1-i.

Line:

total += mat[i][n - 1 - i]

💡 Secondary diagonal elements are accessed by subtracting i from n-1.

insert

Add secondary diagonal element to total

Add mat[0][2] = 3 to total. Total becomes 4.

💡 Adding the secondary diagonal element completes the sum for this row.

Line:

total += mat[i][n - 1 - i]

💡 Both diagonals contribute to the total sum for each row.

traverse

Increment loop: i = 1, select primary diagonal element

Move to row 1, select primary diagonal element mat[1][1] which is 5.

💡 Continue processing next row's primary diagonal element.

Line:

for i in range(n):
    total += mat[i][i]

💡 Primary diagonal elements continue along the main diagonal.

insert

Add primary diagonal element to total

Add mat[1][1] = 5 to total. Total becomes 9.

💡 Add the primary diagonal element from the second row.

Line:

total += mat[i][i]

💡 Total accumulates all primary diagonal elements processed so far.

traverse

Select secondary diagonal element at row 1

Select secondary diagonal element mat[1][1] which is also 5.

💡 Secondary diagonal element overlaps with primary diagonal at center for odd n.

Line:

total += mat[i][n - 1 - i]

💡 Center element is counted twice and will be adjusted later.

insert

Add secondary diagonal element to total

Add mat[1][1] = 5 to total. Total becomes 14.

💡 Add the overlapping center element again; will subtract once later.

Line:

total += mat[i][n - 1 - i]

💡 The center element is temporarily counted twice.

traverse

Increment loop: i = 2, select primary diagonal element

Move to row 2, select primary diagonal element mat[2][2] which is 9.

💡 Process last row's primary diagonal element.

Line:

for i in range(n):
    total += mat[i][i]

💡 Primary diagonal elements continue to the bottom-right corner.

insert

Add primary diagonal element to total

Add mat[2][2] = 9 to total. Total becomes 23.

💡 Add last primary diagonal element to total.

Line:

total += mat[i][i]

💡 Total now includes all primary diagonal elements.

traverse

Select secondary diagonal element at row 2

Select secondary diagonal element mat[2][0] which is 7.

💡 Secondary diagonal element at last row is first column.

Line:

total += mat[i][n - 1 - i]

💡 Secondary diagonal elements move from top-right to bottom-left.

insert

Add secondary diagonal element to total

Add mat[2][0] = 7 to total. Total becomes 30.

💡 Add last secondary diagonal element to total.

Line:

total += mat[i][n - 1 - i]

💡 Total now includes all diagonal elements, but center counted twice.

compare

Check if matrix size is odd to adjust center element

Since n=3 is odd, subtract the center element mat[1][1] = 5 once to avoid double counting.

💡 Center element is counted twice in both diagonals; subtracting once corrects total.

Line:

if n % 2 == 1:
    total -= mat[n//2][n//2]

💡 Adjusting for overlap ensures correct diagonal sum.

shrink

Subtract center element from total

Subtract 5 from total 30, resulting in final total 25.

💡 This step corrects the double counting of the center element.

Line:

total -= mat[n//2][n//2]

💡 Final total now accurately sums both diagonals.

reconstruct

Return final total as answer

Return the computed total 25 as the diagonal sum of the matrix.

💡 Returning the final result completes the algorithm.

Line:

return total

💡 The algorithm outputs the correct sum of both diagonals.

def diagonalSum(mat):
    total = 0  # STEP 1: Initialize total
    n = len(mat)  # STEP 1: Determine matrix size
    for i in range(n):  # STEP 2-13: Loop through rows
        total += mat[i][i]  # STEP 3,7,11: Add primary diagonal element
        total += mat[i][n - 1 - i]  # STEP 4,8,12,13: Add secondary diagonal element
    if n % 2 == 1:  # STEP 14: Check if odd size
        total -= mat[n//2][n//2]  # STEP 15: Subtract center element once
    return total  # STEP 16: Return final total

if __name__ == '__main__':
    matrix = [[1,2,3],[4,5,6],[7,8,9]]
    print(diagonalSum(matrix))  # Output: 25

📊

Matrix Diagonal Sum - Watch the Algorithm Execute, Step by Step

Watching each addition and pointer movement helps you understand how the diagonal elements are accessed and summed without extra space.

setup

0

1

2

Result: 0

compare

left

0

1

2

Result: 0

record

left

0

1

2

Result: 1

compare

i

0

1

right

2

Result: 1

record

i

0

1

right

2

Result: 4

compare

0

left

1

2

Result: 4

record

0

left

1

2

Result: 9

compare

0

right

1

2

Result: 9

record

0

right

1

2

Result: 14

compare

0

1

left

2

Result: 14

record

0

1

left

2

Result: 23

compare

right

0

1

i

2

Result: 23

record

right

0

1

i

2

Result: 30

shrink

0

center

1

2

Result: 30

record

0

center

1

2

Result: 25

record

0

1

2

Result: 25

Key Takeaways

✓ The algorithm efficiently sums both diagonals in a single pass without extra space.

This is hard to see from code alone because the double counting and subtraction of the center element is subtle.

✓ Primary diagonal elements have equal row and column indices, while secondary diagonal elements use n-1-i as the column index.

Visualizing pointer positions clarifies how diagonal elements are accessed.

✓ When n is odd, the center element is counted twice and must be subtracted once to get the correct sum.

The trace shows exactly when and why this adjustment happens, which is easy to miss reading code.

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. You are given an m x n matrix. If an element is 0, you must set its entire row and column to 0 in-place without using extra space proportional to the matrix size. Which approach guarantees an optimal solution with O(1) additional space?

easy

A. Use a greedy approach that zeroes rows and columns immediately when a zero is found during iteration.

B. Use a brute force approach by creating a separate matrix to mark zero positions and then update the original matrix.

C. Use dynamic programming to store zero positions and propagate zeroes through the matrix.

D. Use the first row and first column of the matrix as flags to mark which rows and columns should be zeroed, then update the matrix accordingly.

Solution

1. Step 1: Understand space constraints

   The problem requires in-place modification with O(1) extra space, so approaches using extra matrices or arrays are not optimal.

2. Step 2: Identify the flagging technique

   Using the first row and first column as markers allows tracking which rows and columns to zero without extra space, enabling a single pass update.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   First row/column flagging is a classic O(1) space solution [OK]

Hint: Use matrix edges as flags to save space [OK]

Common Mistakes:

• Zeroing rows/columns immediately loses info about other zeros
• Using extra space arrays violates O(1) space constraint
• Greedy zeroing fails when zeros appear after initial zeroing

3. Given the following code snippet to generate an n x n spiral matrix, what is the value of matrix[1][1] after the function completes when n = 3?

easy

A. 5

B. 9

C. 7

D. 3

Solution

1. Step 1: Trace filling the matrix for n=3

   First row (top=0): fill 1,2,3; then right column (right=2): fill 4,5; then bottom row (bottom=2): fill 6,7; then left column (left=0): fill 8; then top row (top=1): fill 9.

2. Step 2: Identify matrix[1][1]

   After filling outer layers, the center cell matrix[1][1] is assigned the number 5 during the downward fill.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Center cell is the 5th number filled in spiral order [OK]

Hint: Center cell in 3x3 spiral is 5 [OK]

Common Mistakes:

• Confusing indices or direction order
• Off-by-one errors in loops
• Miscounting the fill sequence

4. You are given a square matrix and asked to transform it so that rows become columns and columns become rows without using extra space. Which approach guarantees an optimal in-place solution?

easy

A. Use a brute force approach by creating a new matrix and copying elements accordingly.

B. Swap elements symmetrically across the diagonal only once, iterating over the upper triangle of the matrix.

C. Apply a greedy approach by swapping elements row-wise without considering the diagonal symmetry.

D. Use dynamic programming to store intermediate transposed states and build the final matrix.

Solution

1. Step 1: Understand the problem constraints

   The problem requires an in-place transpose of a square matrix, meaning no extra matrix can be used.

2. Step 2: Identify the correct approach

   Swapping elements symmetrically across the diagonal once (upper triangle only) ensures each pair is swapped exactly once, achieving in-place transpose efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Swapping only upper triangle elements avoids double swaps and extra space [OK]

Hint: Swap only upper triangle elements once [OK]

Common Mistakes:

• Using extra space unnecessarily
• Swapping elements twice by iterating entire matrix
• Ignoring diagonal symmetry leading to incorrect results

5. Suppose the matrix can contain duplicate values and you want to find all lucky numbers (minimum in their row and maximum in their column). Which modification to the optimal approach correctly handles duplicates without missing any lucky numbers?

hard

A. After precomputing row minimums and column maximums, return only the first element matching both conditions per row to avoid duplicates.

B. Use sets to store all minimum values per row and maximum values per column, then find all elements that appear in both sets.

C. Modify the single pass to check if the element equals the row minimum and column maximum, allowing multiple lucky numbers per row or column.

D. Sort each row and column and pick the intersection of minimums and maximums to find lucky numbers.

Solution

1. Step 1: Understand duplicates impact

   Duplicates mean multiple elements in a row can be minimum and multiple in a column can be maximum.

2. Step 2: Modify single pass check

   Instead of returning only one per row, check each element if it equals the row minimum and column maximum, allowing multiple lucky numbers.

3. Step 3: Avoid unnecessary data structures

   Using sets (B) or sorting (D) adds overhead and complexity without benefit. Returning only first match (A) misses valid lucky numbers.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Check all elements against precomputed mins and maxs -> handles duplicates [OK]

Hint: Check all elements, not just first per row [OK]

Common Mistakes:

• Returning only first match per row
• Using extra data structures unnecessarily
• Sorting instead of direct checks