Watch 10 video solutions for Diagonal Traverse, a medium level problem involving Array, Matrix, Simulation. This walkthrough by Algorithms Made Easy has 48,928 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104-105 <= mat[i][j] <= 105Problem Overview: Given an matrix with m x n elements, return all values in diagonal order. The traversal alternates direction for each diagonal: one goes upward-right, the next downward-left, producing a zigzag pattern across the matrix.
Approach 1: Direct Simulation (Time: O(m*n), Space: O(1))
This method simulates the traversal exactly as described. Start from the top-left cell and maintain a direction flag: either moving up-right or down-left. On each step, update the row and column based on the current direction. When you hit a boundary (top row, bottom row, left column, or right column), change direction and adjust the position to the next valid starting point of the following diagonal.
The key insight is that every matrix element belongs to exactly one diagonal step in the traversal. Boundary handling drives the algorithm: if moving up-right and you reach the top edge, shift right and flip direction; if you reach the right edge, move down and flip direction. Similar logic applies when moving down-left. Because each cell is visited once, the runtime is O(m*n) with O(1) auxiliary space besides the output array. This approach works well when you want constant extra memory and clear control over traversal order.
Approach 2: Hash Map of Diagonals (Time: O(m*n), Space: O(m+n))
Every diagonal in a matrix shares the same value of row + col. Iterate through the matrix and group elements using this key in a hash map or list array indexed by row + col. Each key represents one diagonal. After grouping, process the diagonals in order from 0 to m+n-2.
The zigzag requirement comes from reversing elements on alternating diagonals. For even-indexed diagonals, reverse the collected list before appending to the result. For odd ones, keep the order as-is. This technique separates traversal from ordering logic, which simplifies implementation and avoids complex boundary checks.
The algorithm scans the matrix once (O(m*n)) and stores diagonals in a structure with at most m+n-1 groups, resulting in O(m+n) extra space. It relies heavily on concepts from arrays and hash maps to organize elements efficiently.
Recommended for interviews: Direct Simulation is typically what interviewers expect because it demonstrates control over matrix traversal and boundary conditions. The hash map approach is easier to reason about and implement quickly, but it uses additional memory. Showing the simulation first proves you understand how diagonals move through a matrix, while mentioning the grouping trick highlights algorithmic flexibility.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation | O(m*n) | O(1) | Preferred in interviews when you need constant extra memory and precise traversal control |
| Hash Map of Diagonals | O(m*n) | O(m+n) | Cleaner implementation when grouping elements by diagonal index is easier than handling boundaries |