Given a 2D integer array nums, return all elements of nums in diagonal order as shown in the below images.
Example 1:
Input: nums = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,4,2,7,5,3,8,6,9]
Example 2:
Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]] Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]
Constraints:
1 <= nums.length <= 1051 <= nums[i].length <= 1051 <= sum(nums[i].length) <= 1051 <= nums[i][j] <= 105Problem Overview: You receive a jagged 2D list where rows can have different lengths. The task is to return all values in diagonal order. Elements belong to the same diagonal if they share the same row + col index sum. Within a diagonal, elements appear from bottom to top because rows earlier in the matrix must appear later in the traversal.
Approach 1: Hash Map to Group by Diagonals (O(n) time, O(n) space)
The key observation is that every element on the same diagonal has the same r + c value. Iterate through the matrix using nested loops and push each value into a hash map keyed by r + c. Because iteration goes row by row from top to bottom, elements within each diagonal appear in reverse order of the required output. Reverse each stored list (or append to the front during insertion) before adding it to the final result. The total number of processed elements is n, so the traversal and grouping both run in O(n) time with O(n) additional space for storage. This approach primarily relies on Array traversal and hash-based grouping.
Approach 2: Flatten and Sort by Diagonal (O(n log n) time, O(n) space)
Another strategy is to flatten the matrix into a list of tuples containing (r + c, -r, value). The first component groups elements by diagonal, and the negative row index ensures elements deeper in the matrix appear first within each diagonal. After collecting all elements, apply a standard sort. Because sorting compares diagonal index first and row order second, the final sequence naturally produces the required traversal order. Sorting n elements costs O(n log n) time with O(n) extra memory for the flattened structure. This approach highlights how ordering constraints can be handled with Sorting rather than explicit grouping.
Recommended for interviews: The hash map grouping approach is the expected solution. It achieves linear time and clearly demonstrates recognition of the diagonal invariant r + c. Interviewers usually prefer it because the logic is simple and avoids the overhead of sorting. The flatten-and-sort method still works and is often easier to implement quickly, but it trades optimal performance for simplicity. Variants sometimes use a Heap (Priority Queue) to stream elements by diagonal order, though that approach typically performs worse than the direct hash map grouping.
This approach uses a hash map (or dictionary) to group elements that belong to the same diagonal. The sum of indices (i + j) of each element forms a unique key for each diagonal. We iterate over the 2D list, store elements based on their diagonal key, and then read each diagonal to form the result in the required traversal order.
This solution uses a dictionary to store elements by their diagonal key. We compute the diagonal key as the sum of row and column indices. For each diagonal, we store elements in a list. Finally, we sort the keys and concatenate the reversed lists (since lower diagonals need to come first in the result).
Time Complexity: O(N), where N is the total number of elements, as we iterate over each element, and store them in the diagonals dictionary.
Space Complexity: O(N), due to the storage requirement for the diagonals dictionary.
Another approach is to flatten the 2D matrix into a list of triples containing the row index, column index, and value of each element. We then sort this list, prioritizing the sum of indices (i + j), followed by reversing elements when processed within the same diagonal, ensuring the correct order for traversing.
This solution begins by constructing a list of all (row, column, value) triples from the input. It sorts this list by (i + j) as a primary key (for diagonals), and by row in reverse order as a secondary key (to meet traversal requirements), easily extracting values for the result.
Time Complexity: O(N log N) due to sorting operation.
Space Complexity: O(N), storing all elements in a list.
We observe that:
i + j is the same for each diagonal;i + j for the next diagonal is greater than that of the previous diagonal;i + j is the same, and the value of j increases from small to large.Therefore, we store all numbers in the form of (i, j, nums[i][j]) into arr, and then sort according to the first two items. Finally, return the array composed of the values at index 2 of all elements in arr.
The time complexity is O(n times log n), where n is the number of elements in the array nums. The space complexity is O(n).
| Approach | Complexity |
|---|---|
| Hash Map to Group by Diagonals | Time Complexity: O(N), where N is the total number of elements, as we iterate over each element, and store them in the diagonals dictionary. |
| Flatten and Sort by Diagonal | Time Complexity: O(N log N) due to sorting operation. |
| Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map to Group by Diagonals | O(n) | O(n) | Best general solution. Linear traversal and clear diagonal grouping using r+c. |
| Flatten and Sort by Diagonal | O(n log n) | O(n) | Simpler implementation when sorting is acceptable or when quick prototyping. |
Diagonal Traverse II | 2 Approaches | Map | BFS | GOOGLE | Leetcode-1424 • codestorywithMIK • 5,409 views views
Watch 9 more video solutions →Practice Diagonal Traverse II with our built-in code editor and test cases.
Practice on FleetCode