Diagonal Traverse II

Diagonal Traverse II

What is this problem about?

In the Diagonal Traverse II coding problem, you are given a 2D list of integers where each row can have a different length (a "jagged" array). You need to return all elements in diagonal order, starting from the bottom-left of each diagonal and moving up-right. Unlike version I, there is no zig-zagging; every diagonal is traversed in the same direction.

Why is this asked in interviews?

Apple and Amazon use this to test your ability to handle non-rectangular grids. Since you don't know the column length for each row, you cannot easily predict where a diagonal starts or ends. It evaluations your skill in using Hash Tables to group elements by their diagonal index or using BFS to explore the grid level by level.

Algorithmic pattern used

There are two effective patterns:

1. Group by Sum ($r + c$): Iterate through every cell. Store cells in a List<List<Integer>> where the outer list index is $r + c$. Since you visit rows from top to bottom, the elements will naturally be in the reverse order of the required up-right traversal. Reverse each inner list at the end.
2. BFS (Breadth-First Search): Treat the grid as a graph. Start BFS at (0,0). For each cell, its neighbors are the cell below it (only if it's the first column) and the cell to its right.

Example explanation

Grid:

1 2 3
4
5 6

1. (0,0): sum 0. Map: {0: [1]}.
2. (0,1): sum 1. Map: {0: [1], 1: [2]}.
3. (0,2): sum 2. Map: {0: [1], 1: [2], 2: [3]}.
4. (1,0): sum 1. Map: {..., 1: [2, 4]}.
5. (2,0): sum 2. Map: {..., 2: [3, 5]}.
6. (2,1): sum 3. Map: {..., 3: [6]}. Final (after reversing groups): [1, 4, 2, 5, 3, 6].

Common mistakes candidates make

• Creating a Full Matrix: Trying to pad the rows with zeros to make it a rectangle, which can lead to huge memory usage if one row is very long.
• Sorting: Using $O(N \log N)$ sorting on coordinates $(r+c, c)$ instead of $O(N)$ grouping.
• Memory Management: Using a 2D array instead of a Map<Integer, List<Integer>> when the total number of diagonals is large.

Interview preparation tip

For jagged arrays, avoid index-based traversal (for i, for j) if possible. BFS or grouping by an invariant (like $r+c$) are much more robust against varying row lengths.