1424. Diagonal Traverse II

Description

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

 

Solutions

Solution: Array

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[][]} nums
 * @return {number[]}
 */
const findDiagonalOrder = function (nums) {
  const diagonalOrder = [];

  for (const [row, num] of nums.entries()) {
    for (const [col, value] of num.entries()) {
      const order = row + col;
      const diagonal = diagonalOrder[order];

      diagonal ? diagonal.unshift(value) : (diagonalOrder[order] = [value]);
    }
  }
  return diagonalOrder.flat();
};