#1424

Medium

LeetCode Problem Workspace

Diagonal Traverse II

Traverse a jagged 2D array diagonally by grouping elements with equal row and column sums efficiently using sorting and heaps.

array sorting heap priority queue

Problem Statement

Given a 2D integer array nums with variable row lengths, return all elements of nums traversed diagonally. Diagonal traversal groups elements where the sum of the row index and column index is the same, starting from the top-left element and moving along increasing diagonal indices.

For example, given nums = [[1,2,3],[4,5,6],[7,8,9]], the traversal starts at 1, then 4 and 2, followed by 7, 5, 3, continuing diagonally until all elements are included. Handle cases with uneven row lengths and maintain the proper order within each diagonal. Rows may have different lengths, and total elements do not exceed 10^5.

Examples

Example 1

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

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

Example details omitted.

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]

Example details omitted.

Constraints

1 <= nums.length <= 105
1 <= nums[i].length <= 105
1 <= sum(nums[i].length) <= 105
1 <= nums[i][j] <= 105

Solution Approach

Group Elements by Diagonal Index

Iterate through the array and compute row + column for each element, storing elements in a hash map where the key is this diagonal index. This groups all elements that belong to the same diagonal efficiently.

Sort Each Diagonal if Needed

For diagonals where element order matters, sort the values within each hash map entry from bottom to top or left to right as the problem specifies. This ensures correct sequencing when rows have uneven lengths.

Flatten Groups into Result

Iterate over the hash map keys in increasing order of diagonal index and append each sorted group to the result array. This produces the final diagonal traversal array in the correct order.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(\sqrt{n})

Time complexity is O(n) since each element is processed once, and sorting within small diagonals does not exceed O(n) in total. Space complexity is O(\sqrt{n}) because the number of diagonals in a jagged 2D array is bounded by roughly the square root of the total elements.

What Interviewers Usually Probe

Expect candidates to identify the diagonal index pattern using row + column sums.
Watch for correct handling of jagged arrays with varying row lengths.
Candidates should optimize for O(n) traversal without unnecessary nested loops.

Common Pitfalls or Variants

Common pitfalls

Misaligning elements when rows have different lengths causing wrong diagonal grouping.
Sorting each diagonal incorrectly, reversing intended order from bottom to top.
Using extra nested loops instead of mapping diagonal indices, leading to O(n^2) complexity.

Follow-up variants

Diagonal Traverse III with dynamic row additions mid-traversal.
Reverse Diagonal Traversal returning diagonals from bottom-right to top-left.
Weighted Diagonal Traversal applying transformations to elements while maintaining diagonal order.

FAQ

What is the main pattern in Diagonal Traverse II?

The main pattern is grouping array elements by the sum of their row and column indices to traverse diagonally.

How do you handle rows of different lengths in Diagonal Traverse II?

Use a hash map keyed by row + column sum, storing elements for each diagonal; sort each group if necessary before flattening.

Can this be done in O(n) time?

Yes, by processing each element once, grouping by diagonal index, and sorting only small diagonals, overall time remains O(n).

When should a heap be used in this problem?

A heap can be used to maintain order within diagonals when row lengths vary significantly, ensuring elements pop in correct sequence.

What common mistakes occur in diagonal traversal?

Misaligning elements from uneven rows, reversing order in diagonals, or using nested loops leading to O(n^2) time instead of efficient mapping.

terminal

Solution

Solution 1: Sorting

We observe that:

1

2

3

4

5

6

7

8

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        arr = []
        for i, row in enumerate(nums):
            for j, v in enumerate(row):
                arr.append((i + j, j, v))
        arr.sort()
        return [v[2] for v in arr]

Continue Practicing

#1464 maximum product of two elements in an array #1383 maximum performance of a team #1353 maximum number of events that can be attended