Diagonal Traverse

▶

Steps

setup

Initialize matrix dimensions and result array

Calculate the number of rows (m) and columns (n) of the matrix, and initialize an empty result array to store the traversal output.

💡 Knowing matrix size is essential to determine how many diagonals to traverse and to avoid index errors.

Line:

m, n = len(mat), len(mat[0])
result = []

💡 The total number of diagonals will be m + n - 1, which guides the main loop.

traverse

Start first diagonal (d=0)

Set diagonal index d to 0. Calculate the start and end row indices for this diagonal: r_start = max(0, d - n + 1) = 0, r_end = min(d, m - 1) = 0.

💡 Each diagonal covers elements where row + column = d. Calculating r_start and r_end bounds the rows for this diagonal.

Line:

d = 0
r_start = max(0, d - n + 1)
r_end = min(d, m - 1)

💡 For d=0, only one element at (0,0) is on this diagonal.

traverse

Traverse diagonal 0 (even) from r_end down to r_start

Since d=0 is even, traverse from r_end=0 down to r_start=0. Calculate column c = d - r = 0 - 0 = 0. Append mat[0][0] = 1 to result.

💡 Even diagonals are traversed bottom to top, so we move from higher row to lower row indices.

Line:

for r in range(r_end, r_start - 1, -1):
    c = d - r
    result.append(mat[r][c])

💡 The first element appended is 1, starting the diagonal traversal.

traverse

Start second diagonal (d=1)

Increment diagonal index to d=1. Calculate r_start = max(0, 1 - 3 + 1) = 0, r_end = min(1, 2) = 1.

💡 Next diagonal covers elements where row + column = 1, so rows range from 0 to 1.

Line:

d = 1
r_start = max(0, d - n + 1)
r_end = min(d, m - 1)

💡 Diagonal 1 will have two elements: (0,1) and (1,0).

traverse

Traverse diagonal 1 (odd) from r_start up to r_end, append mat[0][1]

Since d=1 is odd, traverse from r_start=0 up to r_end=1. For r=0, c = 1 - 0 = 1. Append mat[0][1] = 2 to result.

💡 Odd diagonals are traversed top to bottom, so row index increases.

Line:

for r in range(r_start, r_end + 1):
    c = d - r
    result.append(mat[r][c])

💡 Appending element 2 continues the diagonal traversal in the correct order.

traverse

Traverse diagonal 1 (odd) continue, append mat[1][0]

Continue traversal for r=1, c = 1 - 1 = 0. Append mat[1][0] = 4 to result.

💡 Continuing top to bottom traversal for odd diagonal.

Line:

for r in range(r_start, r_end + 1):
    c = d - r
    result.append(mat[r][c])

💡 Appending 4 completes diagonal 1 traversal.

traverse

Start third diagonal (d=2)

Increment diagonal index to d=2. Calculate r_start = max(0, 2 - 3 + 1) = 0, r_end = min(2, 2) = 2.

💡 Diagonal 2 covers elements where row + column = 2, rows range from 0 to 2.

Line:

d = 2
r_start = max(0, d - n + 1)
r_end = min(d, m - 1)

💡 Diagonal 2 has three elements: (0,2), (1,1), (2,0).

traverse

Traverse diagonal 2 (even) from r_end down to r_start, append mat[2][0]

Since d=2 is even, traverse from r_end=2 down to r_start=0. For r=2, c = 2 - 2 = 0. Append mat[2][0] = 7 to result.

💡 Even diagonals traverse bottom to top, starting at the largest row index.

Line:

for r in range(r_end, r_start - 1, -1):
    c = d - r
    result.append(mat[r][c])

💡 Appending 7 continues the diagonal traversal correctly.

traverse

Traverse diagonal 2 continue, append mat[1][1]

Continue traversal for r=1, c = 2 - 1 = 1. Append mat[1][1] = 5 to result.

💡 Continuing bottom to top traversal for even diagonal.

Line:

for r in range(r_end, r_start - 1, -1):
    c = d - r
    result.append(mat[r][c])

💡 Appending 5 continues the diagonal traversal.

traverse

Traverse diagonal 2 continue, append mat[0][2]

Continue traversal for r=0, c = 2 - 0 = 2. Append mat[0][2] = 3 to result.

💡 Completing bottom to top traversal for diagonal 2.

Line:

for r in range(r_end, r_start - 1, -1):
    c = d - r
    result.append(mat[r][c])

💡 Appending 3 completes diagonal 2 traversal.

traverse

Start fourth diagonal (d=3)

Increment diagonal index to d=3. Calculate r_start = max(0, 3 - 3 + 1) = 1, r_end = min(3, 2) = 2.

💡 Diagonal 3 covers elements where row + column = 3, rows range from 1 to 2.

Line:

d = 3
r_start = max(0, d - n + 1)
r_end = min(d, m - 1)

💡 Diagonal 3 has two elements: (1,2) and (2,1).

traverse

Traverse diagonal 3 (odd) from r_start up to r_end, append mat[1][2]

Since d=3 is odd, traverse from r_start=1 up to r_end=2. For r=1, c = 3 - 1 = 2. Append mat[1][2] = 6 to result.

💡 Odd diagonals traverse top to bottom, so row index increases.

Line:

for r in range(r_start, r_end + 1):
    c = d - r
    result.append(mat[r][c])

💡 Appending 6 continues the diagonal traversal.

traverse

Traverse diagonal 3 continue, append mat[2][1]

Continue traversal for r=2, c = 3 - 2 = 1. Append mat[2][1] = 8 to result.

💡 Continuing top to bottom traversal for odd diagonal.

Line:

for r in range(r_start, r_end + 1):
    c = d - r
    result.append(mat[r][c])

💡 Appending 8 continues the diagonal traversal.

traverse

Start fifth diagonal (d=4)

Increment diagonal index to d=4. Calculate r_start = max(0, 4 - 3 + 1) = 2, r_end = min(4, 2) = 2.

💡 Diagonal 4 covers elements where row + column = 4, only row 2 is valid.

Line:

d = 4
r_start = max(0, d - n + 1)
r_end = min(d, m - 1)

💡 Diagonal 4 has one element: (2,2).

traverse

Traverse diagonal 4 (even) from r_end down to r_start, append mat[2][2]

Since d=4 is even, traverse from r_end=2 down to r_start=2. For r=2, c = 4 - 2 = 2. Append mat[2][2] = 9 to result.

💡 Even diagonals traverse bottom to top, here only one element.

Line:

for r in range(r_end, r_start - 1, -1):
    c = d - r
    result.append(mat[r][c])

💡 Appending 9 completes the diagonal traversal.

reconstruct

Traversal complete, return result

All diagonals have been traversed and elements appended. The result array now contains the diagonal traversal order.

💡 Returning the result array completes the algorithm.

Line:

return result

💡 The final output matches the expected diagonal traversal order.

from typing import List

def findDiagonalOrder(mat: List[List[int]]) -> List[int]:
    if not mat or not mat[0]:
        return []
    m, n = len(mat), len(mat[0])  # STEP 1
    result = []  # STEP 1
    for d in range(m + n - 1):  # STEP 2 to 15
        r_start = max(0, d - n + 1)  # STEP 2
        r_end = min(d, m - 1)  # STEP 2
        if d % 2 == 0:  # STEP 3, 7, 10, 15
            for r in range(r_end, r_start - 1, -1):  # STEP 3, 7, 9, 10, 15
                c = d - r  # STEP 3, 7, 9, 10, 15
                result.append(mat[r][c])  # STEP 3, 7, 9, 10, 15
        else:  # STEP 5, 6, 12, 13
            for r in range(r_start, r_end + 1):  # STEP 5, 6, 12, 13
                c = d - r  # STEP 5, 6, 12, 13
                result.append(mat[r][c])  # STEP 5, 6, 12, 13
    return result  # STEP 16

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

📊

Diagonal Traverse - Watch the Algorithm Execute, Step by Step

Watching each diagonal traversal and how indices are calculated helps you understand the pattern without guessing or complex direction flags.

setup

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: []

traverse

r_end

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: []

record

c

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1]

traverse

r_start

1

0

r_end

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1]

record

r

1

0

c

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2]

record

c

1

0

r

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2,4]

traverse

r_start

1

0

2

1

r_end

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2,4]

record

c

1

0

2

1

r

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2,4,7]

record

1

0

c

2

1

d

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2,4,7,5]

record

r

1

0

2

1

c

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2,4,7,5,3]

traverse

1

0

r_start

2

1

r_end

3

2

d

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2,4,7,5,3]

record

1

0

r

2

1

c

3

2

d

4

3

5

4

6

5

7

6

8

7

9

8

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

record

1

0

c

2

1

r

3

2

d

4

3

5

4

6

5

7

6

8

7

9

8

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

traverse

1

0

2

1

r_end

3

2

4

3

d

5

4

6

5

7

6

8

7

9

8

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

record

1

0

2

1

c

3

2

4

3

d

5

4

6

5

7

6

8

7

9

8

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

reconstruct

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

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

Key Takeaways

✓ Diagonal traversal can be done without explicit direction flags by using index formulas and parity checks.

This insight is hard to see from code alone because the alternating traversal direction is implicit in the loop ranges.

✓ Each diagonal corresponds to elements where row + column equals the diagonal index, which simplifies boundary calculations.

Understanding this sum property helps visualize why the traversal covers all elements exactly once.

✓ The traversal order alternates between bottom-to-top and top-to-bottom for even and odd diagonals respectively.

Seeing this visually clarifies why the output order zigzags through the matrix.

Practice

1. You are given a matrix sorted in non-increasing order both row-wise and column-wise. The task is to count how many negative numbers are present in the matrix efficiently. Which approach guarantees the optimal time complexity for this problem?

easy

A. Use a brute force nested loop to check every element for negativity.

B. Start from the top-right corner and move left or down based on the sign of the current element.

C. Apply dynamic programming to store counts of negatives in submatrices.

D. Perform a binary search on each row to find the first negative number.

Solution

1. Step 1: Understand matrix properties

   The matrix is sorted in non-increasing order both row-wise and column-wise, so negatives cluster towards the bottom-left.

2. Step 2: Identify optimal traversal

   Starting from the top-right corner allows moving left when a negative is found (to count all negatives below) or down when non-negative, achieving O(m+n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Top-right corner traversal exploits sorting for linear time [OK]

Hint: Top-right corner traversal exploits sorting [OK]

Common Mistakes:

• Using brute force ignoring sorting
• Applying binary search on columns instead of rows
• Trying DP which is unnecessary here

2. Consider the following Python function that computes the sum of the diagonals of a square matrix:

def diagonalSum(mat):
    total = 0
    n = len(mat)
    for i in range(n):
        total += mat[i][i] + mat[i][n - 1 - i]
    if n % 2 == 1:
        total -= mat[n//2][n//2]
    return total

matrix = [[1,2,3],[4,5,6],[7,8,9]]
print(diagonalSum(matrix))

What is the value of total after the loop completes but before the if-condition is applied?

easy

A. 15

B. 25

C. 30

D. 45

Solution

1. Step 1: Trace the loop iterations

   For i=0: total = 0 + mat[0][0] + mat[0][2] = 0 + 1 + 3 = 4 For i=1: total = 4 + mat[1][1] + mat[1][1] = 4 + 5 + 5 = 14 For i=2: total = 14 + mat[2][2] + mat[2][0] = 14 + 9 + 7 = 30

2. Step 2: Note that the if-condition has not yet been applied

   The total before subtracting the center element is 30.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sum of diagonals before center correction is 30 [OK]

Hint: Sum both diagonals first, then adjust center if needed [OK]

Common Mistakes:

• Forgetting to subtract center element once
• Double counting center element
• Off-by-one in indices

3. What is the time complexity of the optimal approach that precomputes row minimums and column maximums and then finds lucky numbers in a matrix of size m x n?

medium

A. O(m * n * (m + n)) because each element is checked against entire row and column.

B. O(m + n) because only minimums and maximums arrays are computed without scanning the entire matrix.

C. O(m * n * log(m + n)) due to sorting rows and columns before checking.

D. O(m * n) because row minimums and column maximums are computed in separate passes and then a single pass finds lucky numbers.

Solution

1. Step 1: Identify complexity of computing row minimums

   Computing min for each of m rows requires O(m * n) time.

2. Step 2: Identify complexity of computing column maximums

   Computing max for each of n columns requires O(m * n) time.

3. Step 3: Single pass to find lucky numbers

   Iterating over all m*n elements to check conditions is O(m * n).

4. Step 4: Combine all steps

   Total time is O(m * n) + O(m * n) + O(m * n) = O(m * n).

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   Precompute and single pass -> linear in matrix size [OK]

Hint: Precompute arrays then single pass -> O(m*n) [OK]

Common Mistakes:

• Confusing brute force complexity with optimal
• Ignoring single pass after precomputation
• Assuming sorting is needed

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