Diagonal Traverse II solution and explanation
Google
9 more videos on this problem
Diagonal Traverse II | 2 Approaches | Map | BFS | GOOGLE | Leetcode-1424codestorywithMIK · 31:46 · 5K views
1424. Diagonal Traverse II | 2 Ways | Matrix Diagonal Trick | BFSAryan Mittal · 17:31 · 5K views
1424. Diagonal Traverse II (Leetcode Medium)Programming Live with Larry · 8:18 · 1K views
Diagonal Traverse II (Leetcode 1424)Coding Interviews · 18:23 · 1K views
Diagonal Traverse II - LeetCode 1424 - PythonAlpha-Code · 15:45 · 1K views
Solving LeetCode 1424 Diagonal Traverse II | Sorting | Google Interview QuestionCode Harmony · 6:26 · 633 views
Daily Leetcode #1331: Nov 22, 2023 - 1424. Diagonal Traverse IIProgramming Live with Larry · 9:38 · 399 views
VISA SDE Interview Questions | LeetCode 1424 Diagonal Traverse IIHow we live in Texas · 12:16 · 274 views
Diagonal Traverse for a list of lists (Leetcode 1424)Algorithms Casts · 15:00 · 267 views
Diagonal Traverse II | 1424 Leetcode | Python3CodeMeThere · 10:11 · 257 views
The problem
Given a 2D integer array nums, return all elements of nums in diagonal order as shown in the below images.
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]
Constraints:
1 <= nums.length <= 1051 <= nums[i].length <= 1051 <= sum(nums[i].length) <= 1051 <= nums[i][j] <= 105
Approach overview
Problem Overview: You receive a jagged 2D list where rows can have different lengths. The task is to return all values in diagonal order. Elements belong to the same diagonal if they share the same row + col index sum. Within a diagonal, elements appear from bottom to top because rows earlier in the matrix must appear later in the traversal.
Approach 1: Hash Map to Group by Diagonals (O(n) time, O(n) space)
The key observation is that every element on the same diagonal has the same r + c value. Iterate through the matrix using nested loops and push each value into a hash map keyed by r + c. Because iteration goes row by row from top to bottom, elements within each diagonal appear in reverse order of the required output. Reverse each stored list (or append to the front during insertion) before adding it to the final result. The total number of processed elements is n, so the traversal and grouping both run in O(n) time with O(n) additional space for storage. This approach primarily relies on Array traversal and hash-based grouping.
Approach 2: Flatten and Sort by Diagonal (O(n log n) time, O(n) space)
Another strategy is to flatten the matrix into a list of tuples containing (r + c, -r, value). The first component groups elements by diagonal, and the negative row index ensures elements deeper in the matrix appear first within each diagonal. After collecting all elements, apply a standard sort. Because sorting compares diagonal index first and row order second, the final sequence naturally produces the required traversal order. Sorting n elements costs O(n log n) time with O(n) extra memory for the flattened structure. This approach highlights how ordering constraints can be handled with Sorting rather than explicit grouping.
Recommended for interviews: The hash map grouping approach is the expected solution. It achieves linear time and clearly demonstrates recognition of the diagonal invariant r + c. Interviewers usually prefer it because the logic is simple and avoids the overhead of sorting. The flatten-and-sort method still works and is often easier to implement quickly, but it trades optimal performance for simplicity. Variants sometimes use a Heap (Priority Queue) to stream elements by diagonal order, though that approach typically performs worse than the direct hash map grouping.
Approach 1: Hash Map to Group by Diagonals
This approach uses a hash map (or dictionary) to group elements that belong to the same diagonal. The sum of indices (i + j) of each element forms a unique key for each diagonal. We iterate over the 2D list, store elements based on their diagonal key, and then read each diagonal to form the result in the required traversal order.
def findDiagonalOrder(nums):
diagonals = {}
for i in range(len(nums)):
for j in range(len(nums[i])):
if (i + j) not in diagonals:
diagonals[i + j] = []
diagonals[i + j].append(nums[i][j])
result = []
for k in sorted(diagonals.keys()):
result.extend(reversed(diagonals[k]))
return resultimport java.util.*;
class Solution {
public List<Integer> findDiagonalOrder(List<List<Integer>> nums) {
Map<Integer, List<Integer>> diagonals = new HashMap<>();
int maxKey = 0;
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums.get(i).size(); j++) {
if (!diagonals.containsKey(i + j)) {
diagonals.put(i + j, new ArrayList<>());
}
diagonals.get(i + j).add(nums.get(i).get(j));
maxKey = Math.max(maxKey, i + j);
}
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i <= maxKey; i++) {
if (diagonals.containsKey(i)) {
Collections.reverse(diagonals.get(i));
result.addAll(diagonals.get(i));
}
}
return result;
}
}#include <vector>
#include <unordered_map>
#include <algorithm>
class Solution {
public:
std::vector<int> findDiagonalOrder(std::vector<std::vector<int>>& nums) {
std::unordered_map<int, std::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]);
maxKey = std::max(maxKey, i + j);
}
}
std::vector<int> result;
for (int i = 0; i <= maxKey; ++i) {
if (diagonals.count(i)) {
std::reverse(diagonals[i].begin(), diagonals[i].end());
result.insert(result.end(), diagonals[i].begin(), diagonals[i].end());
}
}
return result;
}
};var findDiagonalOrder = function(nums) {
let diagonals = {};
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums[i].length; j++) {
if (!(i + j in diagonals)) {
diagonals[i + j] = [];
}
diagonals[i + j].push(nums[i][j]);
}
}
let result = [];
Object.keys(diagonals).sort((a, b) => a - b).forEach(key => {
result.push(...diagonals[key].reverse());
});
return result;
};#include <stdio.h>
#include <stdlib.h>
#define MAX_DIAGONALS 200000
int* findDiagonalOrder(int** nums, int numsSize, int* numsColSize, int* returnSize) {
int** diagonals = malloc(MAX_DIAGONALS * sizeof(int*));
int* diagLengths = calloc(MAX_DIAGONALS, sizeof(int));
int* result = malloc(100000 * sizeof(int));
int count = 0, maxKey = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = 0; j < numsColSize[i]; j++) {
int key = i + j;
if (!diagLengths[key]) {
diagonals[key] = malloc(5000 * sizeof(int));
}
diagonals[key][diagLengths[key]++] = nums[i][j];
if (key > maxKey) maxKey = key;
}
}
for (int key = 0; key <= maxKey; key++) {
for (int i = diagLengths[key] - 1; i >= 0; i--) {
result[count++] = diagonals[key][i];
}
free(diagonals[key]);
}
free(diagonals);
free(diagLengths);
*returnSize = count;
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] FindDiagonalOrder(IList<IList<int>> nums) {
var diagonals = new Dictionary<int, List<int>>();
int maxKey = 0;
foreach (var i in nums)
{
foreach (var j in i)
{
int key = j + nums.IndexOf(i);
if (!diagonals.ContainsKey(key))
{
diagonals[key] = new List<int>();
}
diagonals[key].Add(i[j]);
if (key > maxKey) maxKey = key;
}
}
var result = new List<int>();
for (int key = 0; key <= maxKey; key++)
{
if (diagonals.ContainsKey(key))
{
diagonals[key].Reverse();
result.AddRange(diagonals[key]);
}
}
return result.ToArray();
}
}This solution uses a dictionary to store elements by their diagonal key. We compute the diagonal key as the sum of row and column indices. For each diagonal, we store elements in a list. Finally, we sort the keys and concatenate the reversed lists (since lower diagonals need to come first in the result).
Time Complexity: O(N), where N is the total number of elements, as we iterate over each element, and store them in the diagonals dictionary.
Space Complexity: O(N), due to the storage requirement for the diagonals dictionary.
Approach 2: Flatten and Sort by Diagonal
Another approach is to flatten the 2D matrix into a list of triples containing the row index, column index, and value of each element. We then sort this list, prioritizing the sum of indices (i + j), followed by reversing elements when processed within the same diagonal, ensuring the correct order for traversing.
def findDiagonalOrder(nums):
elements = []
for r, row in enumerate(nums):
for c, val in enumerate(row):
elements.append((r, c, val))
elements.sort(key=lambda x: (x[0] + x[1], -x[0]))
return [val for _, _, val in elements]import java.util.*;
class Solution {
public int[] findDiagonalOrder(List<List<Integer>> nums) {
List<int[]> elements = new ArrayList<>();
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums.get(i).size(); j++) {
elements.add(new int[]{i, j, nums.get(i).get(j)});
}
}
Collections.sort(elements, (a, b) -> {
int cmp = (a[0] + a[1]) - (b[0] + b[1]);
return cmp != 0 ? cmp : b[0] - a[0];
});
int[] result = new int[elements.size()];
for (int k = 0; k < elements.size(); k++) {
result[k] = elements.get(k)[2];
}
return result;
}
}#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<int> findDiagonalOrder(std::vector<std::vector<int>>& nums) {
std::vector<std::tuple<int, int, int>> elements;
for (int i = 0; i < nums.size(); ++i) {
for (int j = 0; j < nums[i].size(); ++j) {
elements.push_back(std::make_tuple(i, j, nums[i][j]));
}
}
std::sort(elements.begin(), elements.end(), [](auto a, auto b) {
int sum1 = std::get<0>(a) + std::get<1>(a);
int sum2 = std::get<0>(b) + std::get<1>(b);
return sum1 == sum2 ? std::get<0>(b) < std::get<0>(a) : sum1 < sum2;
});
std::vector<int> result;
for (auto& elem : elements) {
result.push_back(std::get<2>(elem));
}
return result;
}
};var findDiagonalOrder = function(nums) {
let elements = [];
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums[i].length; j++) {
elements.push([i, j, nums[i][j]]);
}
}
elements.sort((a, b) => {
let sumComp = (a[0] + a[1]) - (b[0] + b[1]);
if (sumComp === 0) {
return b[0] - a[0];
}
return sumComp;
});
return elements.map(e => e[2]);
};typedef struct {
int row, col, value;
} Element;
int compare(const void *a, const void *b) {
Element *ea = (Element *)a;
Element *eb = (Element *)b;
int sum1 = ea->row + ea->col;
int sum2 = eb->row + eb->col;
if (sum1 == sum2) {
return eb->row - ea->row;
}
return sum1 - sum2;
}
int* findDiagonalOrder(int** nums, int numsSize, int* numsColSize, int* returnSize) {
Element *elements = malloc(100000 * sizeof(Element));
int count = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = 0; j < numsColSize[i]; j++) {
elements[count++] = (Element){i, j, nums[i][j]};
}
}
qsort(elements, count, sizeof(Element), compare);
int* result = malloc(count * sizeof(int));
for (int i = 0; i < count; i++) {
result[i] = elements[i].value;
}
free(elements);
*returnSize = count;
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] FindDiagonalOrder(IList<IList<int>> nums) {
var elements = new List<(int, int, int)>();
for (int i = 0; i < nums.Count; i++) {
for (int j = 0; j < nums[i].Count; j++) {
elements.Add((i, j, nums[i][j]));
}
}
elements.Sort((a, b) => {
int cmp = (a.Item1 + a.Item2).CompareTo(b.Item1 + b.Item2);
if (cmp == 0) {
return b.Item1.CompareTo(a.Item1);
}
return cmp;
});
var result = new List<int>();
foreach (var element in elements) {
result.Add(element.Item3);
}
return result.ToArray();
}
}This solution begins by constructing a list of all (row, column, value) triples from the input. It sorts this list by (i + j) as a primary key (for diagonals), and by row in reverse order as a secondary key (to meet traversal requirements), easily extracting values for the result.
Time Complexity: O(N log N) due to sorting operation.
Space Complexity: O(N), storing all elements in a list.
Approach 3: Sorting
We observe that:
- The value of
i + jis the same for each diagonal; - The value of
i + jfor the next diagonal is greater than that of the previous diagonal; - Within the same diagonal, the value of
i + jis the same, and the value ofjincreases from small to large.
Therefore, we store all numbers in the form of (i, j, nums[i][j]) into arr, and then sort according to the first two items. Finally, return the array composed of the values at index 2 of all elements in arr.
The time complexity is O(n times log n), where n is the number of elements in the array nums. The space complexity is O(n).
function findDiagonalOrder(nums: number[][]): number[] {
const arr: number[][] = [];
for (let i = 0; i < nums.length; ++i) {
for (let j = 0; j < nums[i].length; ++j) {
arr.push([i + j, j, nums[i][j]]);
}
}
arr.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));
return arr.map(x => x[2]);
}func findDiagonalOrder(nums [][]int) []int {
arr := [][]int{}
for i, row := range nums {
for j, v := range row {
arr = append(arr, []int{i + j, j, v})
}
}
sort.Slice(arr, func(i, j int) bool {
if arr[i][0] == arr[j][0] {
return arr[i][1] < arr[j][1]
}
return arr[i][0] < arr[j][0]
})
ans := []int{}
for _, v := range arr {
ans = append(ans, v[2])
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Hash Map to Group by Diagonals | Time Complexity: O(N), where N is the total number of elements, as we iterate over each element, and store them in the diagonals dictionary. |
| Flatten and Sort by Diagonal | Time Complexity: O(N log N) due to sorting operation. |
| Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map to Group by Diagonals | O(n) | O(n) | Best general solution. Linear traversal and clear diagonal grouping using r+c. |
| Flatten and Sort by Diagonal | O(n log n) | O(n) | Simpler implementation when sorting is acceptable or when quick prototyping. |
Frequently asked questions
Is Diagonal Traverse II easy or hard?
Diagonal Traverse II is generally classified as a Medium problem. The main challenge is recognizing the diagonal invariant r + c and handling the reversed order within each diagonal, especially with jagged arrays where row lengths differ.
Diagonal Traverse II Python/Java solution
In Python or Java, iterate through each row and column, push values into a map keyed by r + c, then iterate through diagonals in increasing order while reversing each stored list. This produces the required diagonal traversal in O(n) time.
How to solve Diagonal Traverse II in O(n)?
Use the property that elements on the same diagonal share the same r + c value. Traverse the matrix, push each value into a map keyed by r + c, and store them in insertion order. Reverse each diagonal list before appending it to the result to maintain the required bottom-to-top ordering.
What is the best approach for Diagonal Traverse II?
The optimal solution groups elements by the diagonal index r + c using a hash map. Iterate through every element, append it to the list for that diagonal, then output each diagonal in reverse order. This runs in O(n) time and O(n) space where n is the total number of elements.
Is Diagonal Traverse II asked at Google/Amazon/Meta?
Diagonal traversal and matrix indexing problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations that use diagonal grouping (r + c) or coordinate-based ordering are common in system design screening and algorithm rounds.
What data structure is used in Diagonal Traverse II?
The most common implementation uses a hash map where the key is the diagonal index r + c and the value is a list of elements on that diagonal. Arrays or vectors store the values, and the final traversal concatenates each diagonal in reverse order.
What is the time complexity of Diagonal Traverse II?
The optimal hash map grouping approach runs in O(n) time because each element is processed exactly once. Space complexity is O(n) to store diagonal groups before building the result. A sorting-based solution takes O(n log n) time due to sorting all elements.