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:
    def findDiagonalOrder(self, mat):
        M, N = len(mat), len(mat[0])
        TOTAL = M * N
        
        row, col, dirIdx = 0, 0, 0
        rtn = [0] * TOTAL
        
        DIRS = [(-1, 1), (1, -1)]
        
        for i in range(TOTAL):
            rtn[i] = mat[row][col]
            
            nextRow = row + DIRS[dirIdx][0]
            nextCol = col + DIRS[dirIdx][1]
            
            if nextRow < 0 or nextRow >= M or nextCol < 0 or nextCol >= N:
                dirIdx = 1 - dirIdx
                
                if dirIdx == 0:
                    if row == M - 1:
                        col += 1
                    else:
                        row += 1
                else:
                    if col == N - 1:
                        row += 1
                    else:
                        col += 1
            else:
                row = nextRow
                col = nextCol
        
        return rtn

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