Diagonal Traverse II — Solution in Python, Java & C++
Diagonal Traverse II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Diagonal Traverse II is a medium coding problem on arrays, sorting and matrix, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Matrix
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
nums is a jagged 2D array: row i may have any positive length, so some positions (i, j) simply do not exist.
Cell (i, j) lies on anti-diagonal i + j. Return every element of nums read anti-diagonal by anti-diagonal, starting with diagonal 0. Within one diagonal, read from the bottom-most row upwards (larger i first). Positions that do not exist are skipped.
Example 1
Input: nums = [[3,8,1],[6,2,7],[9,4,5]]
Output: [3,6,8,9,2,1,4,7,5]
Example 2
Input: nums = [[5,8],[3],[9,1,7]]
Output: [5,3,8,9,1,7]
Explanation: Diagonal 1 holds `(1,0)` = 3 and `(0,1)` = 8; diagonal 2 holds only `(2,0)` = 9 because rows 0 and 1 are too short.
Example 3
Input: nums = [[4,6,2]]
Output: [4,6,2]
Constraints
1 <= nums.length <= 10^51 <= nums[i].length <= 10^51 <= sum(nums[i].length) <= 10^51 <= nums[i][j] <= 10^5
Hints for Diagonal Traverse II
Hint 1
Every element on the same diagonal shares the same value of
i + j.Hint 2
Group elements by
i + j. In what order should rows be visited so that each group comes out bottom-first?Hint 3
Visit rows from last to first and append each element to bucket
i + j; then concatenate the buckets in order ofi + j.
How to solve Diagonal Traverse II
The output order is a sort by (i + j, -i). Bucketing by i + j achieves it in linear time, and visiting rows from the bottom makes each bucket already ordered.
Approach
- Create a list of buckets indexed by diagonal number.
- Walk the rows from the last one to the first; inside each row walk the columns left to right and append
nums[i][j]to bucketi + j. - Concatenate the buckets from diagonal 0 upwards.
Why it works
Within one bucket, elements arrive in decreasing row order because rows are scanned bottom-up, and a row contributes at most one element to a given diagonal. So each bucket is already in the required bottom-to-top order, and the buckets are output in diagonal order.
Complexity
- Time —
O(N) where N is the total number of elements - Space —
O(N)
Pitfalls
- Walking an
m × maxLenrectangle is far too slow when one row is long and the others are short — only real elements should be touched. - Scanning rows top-down fills each bucket upside down; either reverse each bucket or scan bottom-up.
- The number of diagonals is
max(i + len_i), not the length of the first row.
Reference solution
Python
from typing import List
def findDiagonalOrder(nums: List[List[int]]) -> List[int]:
buckets = []
for i in range(len(nums) - 1, -1, -1):
for j, v in enumerate(nums[i]):
while len(buckets) <= i + j:
buckets.append([])
buckets[i + j].append(v)
out = []
for b in buckets:
out.extend(b)
return outJava
public static int[] findDiagonalOrder(int[][] nums) {
List<List<Integer>> buckets = new ArrayList<>();
int total = 0;
for (int i = nums.length - 1; i >= 0; i--) {
for (int j = 0; j < nums[i].length; j++) {
int d = i + j;
while (buckets.size() <= d) buckets.add(new ArrayList<>());
buckets.get(d).add(nums[i][j]);
total++;
}
}
int[] out = new int[total];
int k = 0;
for (List<Integer> b : buckets) for (int v : b) out[k++] = v;
return out;
}C++
vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
vector<vector<int>> buckets;
for (int i = (int)nums.size() - 1; i >= 0; i--) {
for (int j = 0; j < (int)nums[i].size(); j++) {
int d = i + j;
if ((int)buckets.size() <= d) buckets.resize(d + 1);
buckets[d].push_back(nums[i][j]);
}
}
vector<int> out;
for (auto& b : buckets) for (int v : b) out.push_back(v);
return out;
}JavaScript
var findDiagonalOrder = function(nums) {
var buckets = [];
for (var i = nums.length - 1; i >= 0; i--) {
for (var j = 0; j < nums[i].length; j++) {
var d = i + j;
while (buckets.length <= d) buckets.push([]);
buckets[d].push(nums[i][j]);
}
}
var out = [];
for (var b = 0; b < buckets.length; b++) {
for (var t = 0; t < buckets[b].length; t++) out.push(buckets[b][t]);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms