1424. Diagonal Traverse II

Posted on Edited on In

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:

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

Example 2:

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

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        queue<pair<int, int>> q;
        int m = nums.size();
        vector<int> res;
        q.push({0, 0});
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            res.push_back(nums[x][y]);
            if (y == 0 && x < m - 1) {
                q.emplace(x + 1, 0);
            }
            if (y < nums[x].size() - 1) {
                q.emplace(x, y + 1);
            }
        }
        return res;
    }
};