Skip to main content
Talentd

Diagonal Traverse II - Solution & Explanation

MediumArraySortingHeap (Priority Queue)17 min readAsked at: Amazon, Meta, BP +2
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i].length <= 105
  • 1 <= sum(nums[i].length) <= 105
  • 1 <= nums[i][j] <= 105

Approach Overview

Problem 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.

Approach 1: Hash Map to Group by Diagonals

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).

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Flatten and Sort by Diagonal

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.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

Time Complexity: O(N log N) due to sorting operation.
Space Complexity: O(N), storing all elements in a list.

Try this approach in the editor →

Approach 3: Sorting

We observe that:

  • The value of i + j is the same for each diagonal;
  • The value of i + j for the next diagonal is greater than that of the previous diagonal;
  • Within the same diagonal, the value of 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).

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(N), due to the storage requirement for the diagonals dictionary.

Flatten and Sort by Diagonal

Time Complexity: O(N log N) due to sorting operation.
Space Complexity: O(N), storing all elements in a list.

Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map to Group by DiagonalsO(n)O(n)Best general solution. Linear traversal and clear diagonal grouping using r+c.
Flatten and Sort by DiagonalO(n log n)O(n)Simpler implementation when sorting is acceptable or when quick prototyping.

Video Solution

Diagonal Traverse II | 2 Approaches | Map | BFS | GOOGLE | Leetcode-1424 • codestorywithMIK • 5,631 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Diagonal Traverse II easy or hard?
Diagonal Traverse II is generally classified as a Medium problem. The main challenge is recognizing the diagonal invariant r + c and handling the reversed order within each diagonal, especially with jagged arrays where row lengths differ.
Diagonal Traverse II Python/Java solution
In Python or Java, iterate through each row and column, push values into a map keyed by r + c, then iterate through diagonals in increasing order while reversing each stored list. This produces the required diagonal traversal in O(n) time.
How to solve Diagonal Traverse II in O(n)?
Use the property that elements on the same diagonal share the same r + c value. Traverse the matrix, push each value into a map keyed by r + c, and store them in insertion order. Reverse each diagonal list before appending it to the result to maintain the required bottom-to-top ordering.
What is the best approach for Diagonal Traverse II?
The optimal solution groups elements by the diagonal index r + c using a hash map. Iterate through every element, append it to the list for that diagonal, then output each diagonal in reverse order. This runs in O(n) time and O(n) space where n is the total number of elements.
Is Diagonal Traverse II asked at Google/Amazon/Meta?
Diagonal traversal and matrix indexing problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations that use diagonal grouping (r + c) or coordinate-based ordering are common in system design screening and algorithm rounds.
What data structure is used in Diagonal Traverse II?
The most common implementation uses a hash map where the key is the diagonal index r + c and the value is a list of elements on that diagonal. Arrays or vectors store the values, and the final traversal concatenates each diagonal in reverse order.
What is the time complexity of Diagonal Traverse II?
The optimal hash map grouping approach runs in O(n) time because each element is processed exactly once. Space complexity is O(n) to store diagonal groups before building the result. A sorting-based solution takes O(n log n) time due to sorting all elements.

Ready to solve this problem?

Practice Diagonal Traverse II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays