Diagonal Traverse

LeetCode 498 | Difficulty: Medium

Medium

Problem Description

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

Example 2:

Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]

Constraints:

- `m == mat.length`

- `n == mat[i].length`

- `1 <= m, n <= 10^4`

- `1 <= m * n <= 10^4`

- `-10^5 <= mat[i][j] <= 10^5`

Topics: Array, Matrix, Simulation

---

Approach

Matrix

Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.

When to use

Grid traversal, island problems, path finding, rotating/transforming matrices.

---

Solutions

Solution 1: C# (Best: 376 ms)

Metric	Value
Runtime	376 ms
Memory	N/A
Date	2018-06-27

Solution

public class Solution {
    public int[] FindDiagonalOrder(int[,] matrix) {
        if (matrix.Length == 0) return new int[0];
    int r = 0, c = 0, m = matrix.GetLength(0), n = matrix.GetLength(1);
    int[] arr = new int[m * n];
    for (int i = 0; i < arr.Length; i++)
    {
        arr[i] = matrix[r, c];
        if ((r + c) % 2 == 0)
        {
            // moving up
            if (c == n - 1) { r++; }
            else if (r == 0) { c++; }
            else { r--; c++; }
        }
        else
        {   // moving down
            if (r == m - 1) { c++; }
            else if (c == 0) { r++; }
            else { r++; c--; }
        }
    }
    return arr;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.