Diagonal Traverse II: Grouping by Anti-Diagonals

You are given a 2D integer array nums where each row can have a different length. Your task is to return all elements of the array in diagonal order. The diagonals run from bottom-left to top-right, and you process them left to right across the array.

This is LeetCode 1424: Diagonal Traverse II, a medium-difficulty problem. Unlike the original Diagonal Traverse (LeetCode 498), the input here is a jagged array, meaning rows can vary in length. You cannot simply loop over a fixed m x n grid. That constraint is what makes this problem interesting.

Why this problem matters

Diagonal traversal of a jagged 2D array shows up whenever you need to process elements by their "anti-diagonal index." The pattern appears in matrix-based dynamic programming, image processing, and anywhere you group data by the sum of coordinates. It also tests whether you can handle irregular data structures cleanly, without special-casing every boundary.

The key insight

Every element at position (i, j) in the 2D array sits on the anti-diagonal where i + j equals some constant d. All elements sharing the same d value belong to the same diagonal. Within each diagonal, the problem asks for bottom-to-top order, which means higher row indices come first.

So the algorithm becomes: iterate through every element, group it by its i + j value, and within each group, arrange elements so that larger i values appear before smaller ones. If you iterate row by row from top to bottom, each diagonal group naturally accumulates in top-to-bottom order. You then reverse each group, or you can iterate rows in reverse to get the right order directly.

A cleaner approach: use a defaultdict to collect elements. For each row i (iterated in reverse from the last row to the first), append nums[i][j] to the bucket for key i + j. This way, within each diagonal group, elements are already in bottom-to-top order.

The solution

def findDiagonalOrder(nums: list[list[int]]) -> list[int]:
    from collections import defaultdict

    diagonals = defaultdict(list)
    max_key = 0

    for i in range(len(nums) - 1, -1, -1):
        for j in range(len(nums[i])):
            key = i + j
            diagonals[key].append(nums[i][j])
            max_key = max(max_key, key)

    result = []
    for d in range(max_key + 1):
        result.extend(diagonals[d])

    return result

The outer loop iterates rows in reverse (from the last row up to row 0). For each row, the inner loop walks columns left to right. The diagonal key i + j determines which bucket each element goes into. Because we process rows from bottom to top, elements within each bucket are already in the correct order: bottom-left to top-right along the diagonal.

After grouping, we concatenate all buckets in order of increasing d (from diagonal 0 up to the maximum diagonal index). The result is the full diagonal traversal.

Visual walkthrough

Each step card above shows the key idea: compute i + j for every element, group by that value, then read each group from bottom-left to top-right. The grouping step is where the work happens, and the bottom-to-top ordering within each diagonal comes naturally from iterating rows in reverse.

Complexity analysis

Time: every element is visited exactly once during the grouping pass, and once again during the output pass. Here, n is the total number of elements across all rows. Total time is O(n).

Space: the diagonals dictionary holds every element exactly once, so it uses O(n) space. The result list also holds n elements, but that is required output. Extra space beyond the output is O(n) for the dictionary.

The building blocks

1. Anti-diagonal grouping

The core pattern is grouping 2D coordinates by their anti-diagonal index i + j. This shows up in many matrix problems. Whenever you see "process elements diagonally" or "group by diagonal," reach for this indexing trick.

from collections import defaultdict

diagonals = defaultdict(list)
for i in range(rows):
    for j in range(cols):
        diagonals[i + j].append(matrix[i][j])

This skeleton groups any matrix by anti-diagonals. Adjust the iteration order (top-to-bottom vs. bottom-to-top) depending on which direction you need within each diagonal.

2. BFS-like level processing

An alternative approach treats each diagonal as a "level." You can use a BFS-style traversal where you start from cells in column 0 and expand rightward-upward. Each BFS level corresponds to one anti-diagonal. This works well when the jagged array is very sparse, because BFS only visits cells that actually exist.

Edge cases

Before submitting, make sure your solution handles these:

• Empty input: [] or [[]] should return []. No elements to traverse.
• Single element: [[5]] returns [5]. One diagonal with one element.
• Single row: [[1, 2, 3]] returns [1, 2, 3]. Each element is its own diagonal.
• Single column: [[1], [2], [3]] returns [3, 2, 1]. All on diagonal 0, read bottom-to-top (wait, each is on diagonal i+0 = i, so they are on separate diagonals). Actually, (0,0) has d=0, (1,0) has d=1, (2,0) has d=2, so the result is [1, 2, 3].
• Very jagged arrays: rows with wildly different lengths. The solution handles this naturally because it iterates each row by its own length.
• Large input: with up to 100,000 total elements, the O(n) solution runs comfortably within time limits.

From understanding to recall

You have seen how anti-diagonal grouping works for jagged arrays. The i + j key, the reverse iteration for ordering, the defaultdict accumulation. The logic is clean once you see it, but during a timed interview, you need to produce it without hesitation.

The subtle part is getting the iteration direction right. Top-to-bottom gives you top-to-bottom order within each diagonal, so you would need to reverse. Bottom-to-top gives you the correct order directly. Mixing these up costs you debugging time under pressure.

Spaced repetition locks in the details. You practice writing the grouping loop, the reverse iteration, and the concatenation from scratch. After a few reps, the pattern is automatic. You see "diagonal order" and your fingers write the defaultdict grouping without thinking.

Related posts

• Diagonal Traverse - The predecessor problem with a regular m x n matrix
• Spiral Matrix - Another matrix traversal pattern
• Binary Tree Zigzag Level Order Traversal - Level-based processing in trees

CodeBricks breaks Diagonal Traverse II into its anti-diagonal grouping building block, then drills it independently with spaced repetition. You type the i + j key computation, the reverse-row iteration, and the defaultdict accumulation from scratch until the whole pattern is automatic. When jagged diagonal traversal shows up in your interview, you do not think about it. You just write it.