Skip to main content

Diagonal Traverse II

Problem Description​

Given a 2D integer array nums, return all elements of nums in diagonal order as shown in the below images.

Examples​

Example 1: image

Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,4,2,7,5,3,8,6,9]

Example 2: image

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

Solution for Diagonal Traverse II Problem​

Approach​

The problem requires traversing the 2D list in a diagonal manner. Diagonal order means we visit all elements of each diagonal, starting from the top-left element (0, 0). The diagonals can be visualized as lines of elements where the sum of the row index and column index is constant.

Steps to Solve​

  1. Initialize a Queue and Visited Matrix:

    • Use a queue to facilitate breadth-first traversal starting from the top-left element.
    • Use a visited matrix to keep track of visited elements to avoid processing the same element multiple times.

  2. Determine Dimensions:

    • Determine the maximum number of columns (n) by iterating through each row of the input list.
    • The number of rows (m) is simply the length of the input list.

  3. Breadth-First Traversal:

    • Start from (0, 0), mark it as visited, and add it to the queue.
    • While the queue is not empty, perform the following steps:
      • Dequeue the front element (current position).
      • Add the value at the current position to the result list.
      • Check and enqueue the element directly below the current position if it exists and has not been visited.
      • Check and enqueue the element to the right of the current position if it exists and has not been visited.

  4. Return the Result:

    • After processing all elements in the queue, the result list will contain the elements in diagonal order.

Implementation​

Live Editor
function Solution(arr) {
    function findDiagonalOrder(nums) {
    let ans = [];
    let q = [];
    let vis = nums.map(row => row.map(() => false));

    let m = nums.length;
    let n = 0;
    for (let i = 0; i < m; i++) {
        if (nums[i].length > n) {
            n = nums[i].length;
        }
    }

    q.push([0, 0]);
    vis[0][0] = true;

    while (q.length > 0) {
        let [row, col] = q.shift();
        ans.push(nums[row][col]);

        if (row + 1 < m && col < nums[row + 1].length && !vis[row + 1][col]) {
            q.push([row + 1, col]);
            vis[row + 1][col] = true;
        }
        if (row < m && col + 1 < nums[row].length && !vis[row][col + 1]) {
            q.push([row, col + 1]);
            vis[row][col + 1] = true;
        }
    }

    return ans;
}
  const input = [[1,2,3],[4,5,6],[7,8,9]]
  const output = findDiagonalOrder(input)
  return (
    <div>
      <p>
        <b>Input: </b>
        {JSON.stringify(input)}
      </p>
      <p>
        <b>Output:</b> {output.toString()}
      </p>
    </div>
  );
}
Result
Loading...

Complexity Analysis​

  • Time Complexity: O(m∗n)O(m*n)
  • Space Complexity: O(m∗n) O(m*n)

Code in Different Languages​

Written by @hiteshgahanolia
 findDiagonalOrder(nums) {
     let ans = [];
     let q = [];
     let vis = nums.map(row => row.map(() => false));

     let m = nums.length;
     let n = 0;
     for (let i = 0; i < m; i++) {
         if (nums[i].length > n) {
             n = nums[i].length;
         }
     }

     q.push([0, 0]);
     vis[0][0] = true;

     while (q.length > 0) {
         let [row, col] = q.shift();
         ans.push(nums[row][col]);

         if (row + 1 < m && col < nums[row + 1].length && !vis[row + 1][col]) {
             q.push([row + 1, col]);
             vis[row + 1][col] = true;
         }
         if (row < m && col + 1 < nums[row].length && !vis[row][col + 1]) {
             q.push([row, col + 1]);
             vis[row][col + 1] = true;
         }
     }

     return ans;
 }

References​