1424. Diagonal Traverse II - Detailed Explanation

Problem Statement

You’re given a list of integer lists nums, where each inner list may have different lengths. Imagine these as rows of a ragged matrix. You need to traverse all elements in diagonal order: collect elements on each diagonal (where row+col is constant), but output elements in each diagonal from bottom to top. Return the flattened list of all elements in that diagonal order.

Examples

Example 1

Input: nums = [[1,2,3],
               [4,5],
               [6,7,8,9]]
Output: [1,4,2,6,5,3,7,8,9]

Explanation

• Diagonal 0 (i+j=0): [1] → [1]
• Diagonal 1 (i+j=1): [2,4] → reversed → [4,2]
• Diagonal 2 (i+j=2): [3,5,6] → reversed → [6,5,3]
• Diagonal 3 (i+j=3): [7] → [7]
• Diagonal 4 (i+j=4): [8] → [8]
• Diagonal 5 (i+j=5): [9] → [9]

Example 2

Input: nums = [[1,2,3,4,5]]
Output: [1,2,3,4,5]

Explanation
Only one row, so each element is its own diagonal.

Constraints

• 1 ≤ nums.length ≤ 10⁵ (total rows)
• 1 ≤ nums[i].length ≤ 10⁵
• Sum of all nums[i].length ≤ 10⁵
• -10⁹ ≤ nums[i][j] ≤ 10⁹

Hints

1. Group elements by the sum of their row and column indices (d = i + j).
2. Within each group, you need to output in reverse of insertion order (bottom to top).
3. A hash map from d to a list of values plus a final pass over sorted keys works in O(N) time.

Approaches

Approach 1 Hash Map of Diagonals + Reverse

1. Collect
   • Create an empty map Map<Integer,List<Integer>> diag.
   • For each row index i from 0 to nums.length-1, and each column index j in that row:
     • Compute d = i + j.
     • Append nums[i][j] to diag.get(d).
2. Flatten
   • Create an output list res.
   • For each diagonal index d in increasing order:
     • Retrieve the list lst = diag.get(d).
     • Iterate lst in reverse and append each value to res.
3. Return res.

Step‐by‐Step Walkthrough for Example 1

nums = [[1,2,3],
        [4,5],
        [6,7,8,9]]

Pass 1: collect into diag  
 d=0 → [1]  
 d=1 → [2]  
 d=2 → [3]  
 d=1 → [2,4]  
 d=2 → [3,5]  
 d=3 → [7]  
 d=2 → [3,5,6]  
 d=3 → [7,8]  
 d=4 → [9]

But careful by rows:
i=0: j=0→d0:[1], j=1→d1:[2], j=2→d2:[3]
i=1: j=0→d1:[2,4], j=1→d2:[3,5]
i=2: j=0→d2:[3,5,6], j=1→d3:[7], j=2→d4:[8], j=3→d5:[9]

Pass 2: flatten in key order  
 d=0: [1]                 → [1]  
 d=1: [2,4] reversed → [4,2]  
 d=2: [3,5,6] reversed → [6,5,3]  
 d=3: [7]                 → [7]  
 d=4: [8]                 → [8]  
 d=5: [9]                 → [9]  

Result → [1,4,2,6,5,3,7,8,9]

Complexity

• Time O(N) to traverse all elements + O(D) to iterate diagonals, where N = total elements and D = number of diagonals (≤N).
• Space O(N) for the map and result.

Approach 2 Priority Queue by (diagonal, −row)

1. For every element (i,j), push (i+j, -i, value) into a min-heap.
2. Pop all elements in heap order, collecting value.
3. This automatically orders first by i+j, then by larger i first (because of -i).

Complexity

• Time O(N log N) due to heap operations.
• Space O(N).

Common Mistakes

• Not reversing each diagonal’s list → yields top‑to‑bottom instead of bottom‑to‑top.
• Assuming rectangular matrix → inner lists may differ in length.
• Using TreeMap on every access → slower than collecting keys once.

Python Code