Diagonal Traverse II - Video Solutions

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.