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

Examples

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

Thinking Process

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

  • Treat the grid as a graph with 4- or 8-directional neighbors.
  • Row-major vs column-major traversal affects cache and logic.
  • Boundary checks on every neighbor expansion.
Grid traversal BFS/DFS flood from each cell

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Row/column traversal (this problem) O(nm) O(1) Simulation, spiral
BFS/DFS on grid O(nm) O(nm) Islands, shortest path
Matrix as graph O(nm) O(nm) 4/8-directional neighbors
Transpose / rotate O(nm) O(1) In-place rotation tricks

Solution

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        const int M = mat.size(), N = mat[0].size();
        const int TOTAL = M * N;
        int row = 0, col = 0, dirIdx = 0;
        vector<int> rtn(TOTAL);
        for(int i = 0; i < TOTAL; i++) {
            rtn[i] = mat[row][col];
            int nextRow = row + DIRS[dirIdx][0];
            int nextCol = col + DIRS[dirIdx][1];
            if(nextRow < 0 || nextRow >= M || nextCol < 0 || nextCol >= N) {
                dirIdx = 1 - dirIdx;
                if(dirIdx == 0) {
                    if(row == M - 1) col++;
                    else row++;
                } else {
                    if(col == N - 1) row++;
                    else col++;
                }
            } else{
                row = nextRow;
                col = nextCol;
            }
        }
        return rtn;
    }
private:
    const vector<vector<int>> DIRS = {{-1, 1}, {1, -1}};
};

Solution Explanation

Approach: Row/column traversal (this problem)

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

How the code works:

  • Treat the grid as a graph with 4- or 8-directional neighbors.
  • Row-major vs column-major traversal affects cache and logic.
  • Boundary checks on every neighbor expansion.

Walkthrough — input mat = [[1,2,3],[4,5,6],[7,8,9]], expected output [1,2,4,7,5,3,6,8,9]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.
  • Time Complexity: O(m × n) — visit each cell exactly once
  • Space Complexity: O(1) extra space (excluding the output array)

    Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  • Pattern: Row/column traversal (this problem)
  • Treat the grid as a graph with 4- or 8-directional neighbors.
  • Row-major vs column-major traversal affects cache and logic.

References

Template Reference