Diagonal Traverse II

Description

Given a list of lists of integers, 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]

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 <= nums[i][j] <= 10^9
• There at most 10^5 elements in nums.

Solution(javascript)

// /** 1: 记录每一层的位置
//  * @param {number[][]} nums
//  * @return {number[]}
//  */
// const findDiagonalOrder = function (nums) {
//   const result = []
//   let level = -1
//   for (let i = 0; i < nums.length; i++) {
//     level += 1
//     for (let j = 0; j < nums[i].length; j++) {
//       result[level + j] = result[level + j] || []
//       result[level + j].push(nums[i][j])
//     }
//   }
//   return result.reduce((acc, items) => {
//     acc.push(...items.reverse())
//     return acc
//   }, [])
// }


/** 2: BFS
 * @param {number[][]} nums
 * @return {number[]}
 */
const findDiagonalOrder = function (nums) {
  const result = [nums[0][0]]
  let current = [[0, 0]]
  const visited = {
    '0-0': true,
  }
  while (current.length > 0) {
    const next = []
    const push = (row, column) => {
      const key = `${row}-${column}`
      if (!visited[key] && nums[row] && nums[row][column] !== undefined) {
        visited[key] = true
        next.push([row, column])
        result.push(nums[row][column])
      }
    }
    for (const [row, column] of current) {
      push(row + 1, column)
      push(row, column + 1)
    }
    current = next
  }
  return result
}