Practice/Meta/Leetcode 1424. Diagonal Traverse II

Leetcode 1424. Diagonal Traverse II

CodingMust

Problem

Given a 2D array of integers where rows can have different lengths (a jagged array), return all elements in diagonal order.

The traversal pattern follows anti-diagonals from top-left to bottom-right. Elements that share the same diagonal have the same sum of their row and column indices (i + j). Process diagonals in ascending order by their sum, and within each diagonal, process elements in the order they appear from top to bottom.

For example, in a standard grid, the element at position (0,0) is on diagonal 0, positions (0,1) and (1,0) are on diagonal 1, positions (0,2), (1,1), and (2,0) are on diagonal 2, and so on.

Requirements

1. Traverse the array by anti-diagonals (where i+j defines the diagonal)
2. Process diagonals in increasing order of their sum
3. Within each diagonal, maintain the top-to-bottom row order
4. Handle jagged arrays where different rows have different lengths
5. Return a flat list of all elements in the specified order

Constraints

• 1 ≤ nums.length ≤ 10^5
• 1 ≤ nums[i].length ≤ 10^5
• 1 ≤ sum of all nums[i].length ≤ 10^5
• 1 ≤ nums[i][j] ≤ 10^9
• Time complexity: O(N) where N is the total number of elements
• Space complexity: O(N) for the result

Examples

Example 1:

Input: nums = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,4,2,7,5,3,8,6,9] Explanation: Diagonal 0 (i+j=0): [1] Diagonal 1 (i+j=1): [4,2] Diagonal 2 (i+j=2): [7,5,3] Diagonal 3 (i+j=3): [8,6] Diagonal 4 (i+j=4): [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] Explanation: The array is jagged but we still group by i+j diagonal sum

Example 3:

Input: nums = [[1,2],[3],[],[4,5,6]] Output: [1,3,2,4,5,6] Explanation: Empty rows are skipped during traversal