Problem Description

In the Leetcode problem Diagonal Traverse II, you are given a list of lists of integers called nums, where each inner list represents a row in a 2D array. The 2D array is jagged, meaning that rows can have different lengths. Your task is to return all the elements of nums in diagonal order as described below:

• The elements are traversed along diagonals going from the top-left to the bottom-right.
• For each diagonal, elements are processed in order from the bottommost row up to the topmost row.
• You must not reuse elements, and every element in nums must appear exactly once in the output.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i].length <= min(10^5, 10^5 - sum_{j=0}^{i-1} nums[j].length)
• The total number of elements across all rows does not exceed 10^5.

The problem guarantees that there is only one valid output order.

Thought Process

To solve this problem, we need to understand how the diagonal traversal works for a jagged 2D array. In a regular matrix, the diagonal index for an element at (i, j) is simply i + j. All elements with the same i + j lie on the same diagonal. However, since nums can have rows of different lengths, we cannot assume a rectangular shape or use simple row/column iteration.

The brute-force approach would be to flatten the array and sort the elements by their diagonal index, but this would be inefficient. Instead, we look for a way to group elements by their diagonal index as we iterate through nums. For each diagonal, we must process elements from bottom to top, which means as we collect elements, we need to reverse their order per diagonal before outputting them.

This leads us to consider using a hash map (dictionary) to group elements by diagonal, then outputting the diagonals in order. The key insight is that we can process each element once, group them efficiently, and then flatten the groups in the correct order.

Solution Approach

We can break the solution into the following steps:

1. Iterate through nums: For each element at position (i, j) in nums, compute the diagonal index as d = i + j.
2. Group elements by diagonal: Use a hash map (dictionary) where the key is the diagonal index d, and the value is a list of elements that fall on that diagonal. Since we want to output elements from bottom to top, we append elements as we find them, and later reverse each list.
3. Flatten the diagonals: Iterate through the diagonals in increasing order of their index. For each diagonal, reverse the list of elements (to get bottom-to-top order), and append them to the final result.
4. Return the result: The resulting list contains all elements in the required diagonal traversal order.

This approach ensures that every element is visited exactly once, and that the output order matches the problem's requirements.

Example Walkthrough

Let's walk through an example:

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

• For element 1 at (0, 0): diagonal = 0+0 = 0
• For element 2 at (0, 1): diagonal = 0+1 = 1
• For element 3 at (0, 2): diagonal = 0+2 = 2
• For element 4 at (1, 0): diagonal = 1+0 = 1
• For element 5 at (1, 1): diagonal = 1+1 = 2
• For element 6 at (1, 2): diagonal = 1+2 = 3
• For element 7 at (2, 0): diagonal = 2+0 = 2
• For element 8 at (2, 1): diagonal = 2+1 = 3
• For element 9 at (2, 2): diagonal = 2+2 = 4

Grouping by diagonal:

• Diagonal 0: [1]
• Diagonal 1: [2, 4]
• Diagonal 2: [3, 5, 7]
• Diagonal 3: [6, 8]
• Diagonal 4: [9]

For each diagonal, reverse the list to get bottom-to-top order:

• Diagonal 0: [1]
• Diagonal 1: [4, 2]
• Diagonal 2: [7, 5, 3]
• Diagonal 3: [8, 6]
• Diagonal 4: [9]

The final answer is: [1, 4, 2, 7, 5, 3, 8, 6, 9]

Code Implementation

from collections import defaultdict
class Solution:
    def findDiagonalOrder(self, nums):
        diagonals = defaultdict(list)
        for i, row in enumerate(nums):
            for j, val in enumerate(row):
                diagonals[i + j].append(val)
        result = []
        for d in sorted(diagonals.keys()):
            # Reverse to get bottom-to-top order
            result.extend(reversed(diagonals[d]))
        return result
      

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        unordered_map<int, vector<int>> diagonals;
        int maxKey = 0;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = 0; j < nums[i].size(); ++j) {
                diagonals[i + j].push_back(nums[i][j]);
                if (i + j > maxKey) maxKey = i + j;
            }
        }
        vector<int> result;
        for (int d = 0; d <= maxKey; ++d) {
            if (diagonals.count(d)) {
                auto& diag = diagonals[d];
                result.insert(result.end(), diag.rbegin(), diag.rend());
            }
        }
        return result;
    }
};
      

import java.util.*;
class Solution {
    public int[] findDiagonalOrder(List<List<Integer>> nums) {
        Map<Integer, List<Integer>> diagonals = new HashMap<>();
        int total = 0, maxKey = 0;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = 0; j < nums.get(i).size(); ++j) {
                int idx = i + j;
                diagonals.computeIfAbsent(idx, k -> new ArrayList<>()).add(nums.get(i).get(j));
                if (idx > maxKey) maxKey = idx;
                total++;
            }
        }
        int[] result = new int[total];
        int pos = 0;
        for (int d = 0; d <= maxKey; ++d) {
            if (diagonals.containsKey(d)) {
                List<Integer> diag = diagonals.get(d);
                for (int k = diag.size() - 1; k >= 0; --k) {
                    result[pos++] = diag.get(k);
                }
            }
        }
        return result;
    }
}
      

var findDiagonalOrder = function(nums) {
    const diagonals = new Map();
    let maxKey = 0;
    for (let i = 0; i < nums.length; ++i) {
        for (let j = 0; j < nums[i].length; ++j) {
            const idx = i + j;
            if (!diagonals.has(idx)) diagonals.set(idx, []);
            diagonals.get(idx).push(nums[i][j]);
            if (idx > maxKey) maxKey = idx;
        }
    }
    const result = [];
    for (let d = 0; d <= maxKey; ++d) {
        if (diagonals.has(d)) {
            const diag = diagonals.get(d);
            for (let k = diag.length - 1; k >= 0; --k) {
                result.push(diag[k]);
            }
        }
    }
    return result;
};
      

Time and Space Complexity

Brute-force approach:

• Flattening all elements and sorting them by diagonal index would take O(N log N) time, where N is the total number of elements.
• Space complexity would also be O(N) for storing all elements and their indices.

• Time complexity: O(N), because we visit each element once to group them, and then once more to flatten the result.
• Space complexity: O(N), as we store all elements in the hash map before outputting them.

This is optimal since every element must be output exactly once.

Summary

The diagonal traversal of a jagged 2D array can be solved efficiently by grouping elements by their diagonal index (i + j), and then processing each group in reverse order to satisfy the "bottom-to-top" requirement. This approach leverages a hash map for efficient grouping and ensures that the solution is both time and space optimal. The key insight is recognizing the diagonal grouping and the need to reverse the order within each group, making the solution both elegant and efficient.