Diagonal Traverse II

Medium
1549.

Diagonal Traverse II

Diagonal Traverse II is a medium coding problem on arrays, sorting and matrix, asked in Amazon, Google and Meta interviews.

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^5
  • 1 <= nums[i].length <= 10^5
  • 1 <= sum(nums[i].length) <= 10^5
  • 1 <= nums[i][j] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} nums
 * @return {number[]}
 */
var findDiagonalOrder = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= nums[i].length <= 10^5
  • 1 <= sum(nums[i].length) <= 10^5
  • 1 <= nums[i][j] <= 10^5

Hints for Diagonal Traverse II

  1. Hint 1

    Every element on the same diagonal shares the same value of i + j.

  2. Hint 2

    Group elements by i + j. In what order should rows be visited so that each group comes out bottom-first?

  3. Hint 3

    Visit rows from last to first and append each element to bucket i + j; then concatenate the buckets in order of i + 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

  1. Create a list of buckets indexed by diagonal number.
  2. 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 bucket i + j.
  3. 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 × maxLen rectangle 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 out

Java

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