Diagonal Traverse II
Medium · Matrix · Array · Matrix · Breadth-First Search
Problem
You are given a jagged 2D integer array nums: rows may have different lengths. Group the cells by anti-diagonal, the value of row + col, and visit the groups in increasing order of row + col.
Within one anti-diagonal, visit the cells from the bottom-most row upward (largest row index first). Return all elements in this order.
Examples
Input: nums = [[1,2,3],[4,5],[6]] Output: [1,4,2,6,5,3]
Diagonal 0 is [1], diagonal 1 is 4 then 2, diagonal 2 is 6, 5, 3 from the bottom up.
Input: nums = [[1,2],[3],[4,5,6]] Output: [1,3,2,4,5,6]
Diagonal 1 is 3 then 2. Diagonal 2 holds only 4, because rows 0 and 1 are too short; 5 and 6 each sit alone on later diagonals.
Input: nums = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,4,2,7,5,3,8,6,9]
A full square: 1, then 4 2, then 7 5 3, then 8 6, then 9.
Constraints
- 1 <= len(nums) <= 10^5
- 1 <= len(nums[i]) <= 10^5
- the total number of elements is at most 10^5
- 1 <= nums[i][j] <= 10^5
Approaches
- Walk every diagonal through every row — time O(D · R), D diagonals, R rows, space O(1) besides the answer
Follow-up
Sorting the cells by (row + col, -row) also works, in O(N log N). The bucket and BFS solutions avoid the sort because the keys are small integers and the order inside a bucket comes for free.
Related problems
Start free on Cariara · Coding problems · System design studio
