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.
This approach involves a direct simulation of the diagonal traversal. We use two variables, i and j, to represent the current position in the matrix, and a boolean direction to indicate whether we are moving upwards or downwards diagonally. The process toggles the direction once the boundaries of the matrix are reached, ensuring that the entire matrix is traversed correctly in a zig-zag order.
This C solution simulates diagonal traversal by using a loop that runs until all elements in mat are processed. By switching the direction based on boundary conditions, the code alternates between moving upwards and downwards along diagonals. The final result is stored in an array which is returned.
Time Complexity: O(m * n) as each element is processed once.
Space Complexity: O(m * n) needed for the output array.
This approach leverages a hash map (or dictionary) to collect elements that belong to the same diagonal. The sum of the row and column indices i + j serves as the key, grouping all elements located on the same diagonal. After populating the hash map, we extract and append these elements to the result array, reversing them as needed to maintain the diagonal order.
This C implementation collects elements into arrays stored for each diagonal sum i + j using a dynamic allocation system. After filling these arrays, it extracts and appropriately reverses elements for diagonal order.
Time Complexity: O(m * n), visits each element once.
Space Complexity: O(m * n), required for temporary storage for diagonals.
For each round k, we fix the starting point from the top-right and traverse diagonally to the bottom-left to get t. If k is even, we reverse t.
The time complexity is O(m times n), and the space complexity is O(1). Ignoring the space used for the answer.
| Approach | Complexity |
|---|---|
| Approach 1: Direct Simulation | Time Complexity: O(m * n) as each element is processed once. |
| Approach 2: Hash Map of Diagonals | Time Complexity: O(m * n), visits each element once. |
| Fixed Point Traversal | — |
| 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 |
Diagonal Traverse | Live Coding with Explanation | Leetcode - 498 • Algorithms Made Easy • 58,707 views views
Watch 9 more video solutions →Practice Diagonal Traverse with our built-in code editor and test cases.
Practice on FleetCode