[Medium] 1424. Diagonal Traverse II

Given a 2D integer array nums, return all elements of nums in diagonal order.

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 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 3:

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

Example 4:

Input: nums = [[1,2,3,4,5,6]]
Output: [1,2,3,4,5,6]

Constraints

1 <= nums.length <= 10^5
1 <= nums[i].length <= 10^5
1 <= sum(nums[i].length) <= 10^5
1 <= nums[i][j] <= 10^9

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

Diagonal definition: What defines a diagonal? (Assumption: Elements at same (row + col) sum are on same diagonal - diagonal index = i + j)
Traversal order: What is the traversal order? (Assumption: Traverse diagonals from top-left to bottom-right, within each diagonal from bottom to top)
Array structure: Can rows have different lengths? (Assumption: Yes - per constraints, nums[i].length can vary)
Return format: What should we return? (Assumption: 1D array with elements in diagonal traversal order)
Empty array: What if array is empty? (Assumption: Return empty array)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Traverse the 2D array row by row, and for each element, calculate its diagonal index (row + col). Store elements in a 2D structure indexed by diagonal, then flatten the result. However, since rows have different lengths, we need to handle out-of-bounds carefully. This approach works but requires extra space to store elements by diagonal, and the traversal order needs careful handling to get the correct bottom-to-top order within each diagonal.

Step 2: Semi-Optimized Approach (7 minutes)

Use BFS starting from (0,0). For each diagonal level, process all elements at that level. Maintain a queue of (row, col) pairs, and for each level, collect all elements with the same (row + col) sum. However, BFS naturally processes level by level, but we need to process diagonals in order and within each diagonal from bottom to top, which requires additional sorting or careful queue management.

Step 3: Optimized Solution (8 minutes)

Use a hash map to group elements by their diagonal index (row + col). Iterate through the 2D array, adding each element to its corresponding diagonal bucket. Then, iterate through diagonals in order (0, 1, 2, …), and for each diagonal, iterate through rows from bottom to top (larger row index first) to get the correct traversal order. This achieves O(n) time where n is the total number of elements, and O(n) space for the hash map. The key insight is that diagonal index = row + col uniquely identifies each diagonal, and within each diagonal, processing rows in reverse order gives the bottom-to-top traversal we need.

Solution: Hash Map Grouping and BFS Approaches

Time Complexity: O(n) where n is total number of elements
Space Complexity: O(n)

We can solve this problem using two approaches:

Hash Map Grouping: Group elements by their diagonal index (row + col), then iterate through diagonals in order.
BFS Traversal: Use a queue to traverse diagonally, processing elements level by level.

Solution 1: Hash Map Grouping (C++20 Optimized)

Key Insight: Elements on the same diagonal have the same sum of row and column indices (row + col). We can group all elements by this diagonal index, then iterate through diagonals in ascending order.

using namespace std;

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        unordered_map<int, vector<int>> groups;
        
        // Traverse from bottom to top to maintain diagonal order
        for (int row = (int)nums.size() - 1; row >= 0; row--) {
            for (int col = 0; col < (int)nums[row].size(); col++) {
                int diagonal = row + col;
                groups[diagonal].push_back(nums[row][col]);
            }
        }
        
        vector<int> rtn;
        rtn.reserve(nums.size() * nums[0].size());
        
        // Process diagonals in order (0, 1, 2, ...)
        int curr = 0;
        while (groups.find(curr) != groups.end()) {
            for (int num : groups[curr]) {
                rtn.push_back(num);
            }
            curr++;
        }
        
        return rtn;
    }
};

C++20 Optimizations:

groups.find(curr) != groups.end() for map lookup (C++20 compatible)
reserve() to pre-allocate memory for efficiency
Range-based for loops for cleaner iteration

How it works:

Group by Diagonal: For each element at (row, col), calculate diagonal = row + col and add it to the corresponding group.
Bottom-to-Top Traversal: We traverse rows from bottom to top so that when we process diagonals in order, elements appear in the correct sequence.
Sequential Processing: Process diagonals starting from 0, adding all elements in each diagonal group to the result.

Solution 2: BFS Traversal (C++20 Optimized)

Key Insight: We can use BFS starting from (0, 0) and traverse diagonally. For each cell, we explore:

The cell below (if in first column): (row + 1, 0)
The cell to the right: (row, col + 1)

using namespace std;

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        queue<pair<int, int>> q;
        q.push({0, 0});
        vector<int> rtn;
        rtn.reserve(nums.size() * nums[0].size());
        
        while (!q.empty()) {
            auto [row, col] = q.front();
            q.pop();
            
            rtn.push_back(nums[row][col]);
            
            // If in first column, add cell below
            if (col == 0 && row + 1 < (int)nums.size()) {
                q.push({row + 1, col});
            }
            
            // Add cell to the right
            if (col + 1 < (int)nums[row].size()) {
                q.push({row, col + 1});
            }
        }
        
        return rtn;
    }
};

C++20 Optimizations:

Structured bindings auto [row, col] for pair unpacking (C++17)
reserve() for memory pre-allocation
Simplified type casting with (int) instead of static_cast<int>()

How it works:

Start at Origin: Begin BFS from (0, 0).
Process Current Cell: Add the current cell’s value to the result.
Explore Neighbors:
- If in the first column (col == 0), add the cell below: (row + 1, 0)
- Always add the cell to the right: (row, col + 1)
Continue BFS: Process all cells in the queue until empty.

Step-by-Step Example

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

Solution 1: Hash Map Approach

Step	Row	Col	Diagonal	Groups
1	2	0	2	`{2: [7]}`
2	2	1	3	`{2: [7], 3: [8]}`
3	2	2	4	`{2: [7], 3: [8], 4: [9]}`
4	1	0	1	`{1: [4], 2: [7], 3: [8], 4: [9]}`
5	1	1	2	`{1: [4], 2: [7,5], 3: [8], 4: [9]}`
6	1	2	3	`{1: [4], 2: [7,5], 3: [8,6], 4: [9]}`
7	0	0	0	`{0: [1], 1: [4], 2: [7,5], 3: [8,6], 4: [9]}`
8	0	1	1	`{0: [1], 1: [4,2], 2: [7,5], 3: [8,6], 4: [9]}`
9	0	2	2	`{0: [1], 1: [4,2], 2: [7,5,3], 3: [8,6], 4: [9]}`

Processing diagonals:

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

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

Solution 2: BFS Approach

Step	Queue	Process	Result	Next Moves
0	`[(0,0)]`	-	`[]`	-
1	`[(0,0)]`	`(0,0)` → 1	`[1]`	`(1,0), (0,1)`
2	`[(1,0), (0,1)]`	`(1,0)` → 4	`[1,4]`	`(2,0), (1,1)`
3	`[(0,1), (2,0), (1,1)]`	`(0,1)` → 2	`[1,4,2]`	`(0,2)`
4	`[(2,0), (1,1), (0,2)]`	`(2,0)` → 7	`[1,4,2,7]`	`(2,1)`
5	`[(1,1), (0,2), (2,1)]`	`(1,1)` → 5	`[1,4,2,7,5]`	`(1,2)`
6	`[(0,2), (2,1), (1,2)]`	`(0,2)` → 3	`[1,4,2,7,5,3]`	-
7	`[(2,1), (1,2)]`	`(2,1)` → 8	`[1,4,2,7,5,3,8]`	`(2,2)`
8	`[(1,2), (2,2)]`	`(1,2)` → 6	`[1,4,2,7,5,3,8,6]`	-
9	`[(2,2)]`	`(2,2)` → 9	`[1,4,2,7,5,3,8,6,9]`	-

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

Visual Representation

Matrix:
    0  1  2
0 [ 1  2  3 ]
1 [ 4  5  6 ]
2 [ 7  8  9 ]

Diagonals (row + col):
    0  1  2
0 [ 0  1  2 ]
1 [ 1  2  3 ]
2 [ 2  3  4 ]

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

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

Key Insights

Diagonal Property: Elements on the same diagonal share the same row + col sum.
Traversal Order: Bottom-to-top traversal ensures correct ordering when processing diagonals sequentially.
BFS Alternative: BFS naturally explores diagonals when we prioritize right moves over down moves.
Jagged Arrays: Both solutions handle jagged arrays (rows of different lengths) correctly.

Complexity Analysis

Solution 1: Hash Map

Time: O(n) - Each element is visited once
Space: O(n) - Hash map stores all elements

Solution 2: BFS

Time: O(n) - Each element is processed once
Space: O(n) - Queue can contain up to O(n) elements in worst case

When to Use Each Approach

Hash Map Approach: More intuitive, easier to understand the diagonal grouping concept.
BFS Approach: More natural for graph-like traversal, but requires careful neighbor selection logic.

Both approaches are efficient and handle jagged arrays well. Choose based on your preference and coding style.

Robina Li

[Medium] 1424. Diagonal Traverse II

[Medium] 1424. Diagonal Traverse II

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Solution: Hash Map Grouping and BFS Approaches

Solution 1: Hash Map Grouping (C++20 Optimized)

Solution 2: BFS Traversal (C++20 Optimized)

Step-by-Step Example

Solution 1: Hash Map Approach

Solution 2: BFS Approach

Visual Representation

Key Insights

Complexity Analysis

Solution 1: Hash Map

Solution 2: BFS

When to Use Each Approach

Related Posts

Recent Posts