1424

1424. Diagonal Traverse II (Medium)

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

Companies: Facebook, VMware, Google

Related Topics:
Array, Sorting, Heap (Priority Queue)

Hints:

• Notice that numbers with equal sums of row and column indexes belong to the same diagonal.
• Store them in tuples (sum, row, val), sort them, and then regroup the answer.

Solution 1.

At each level, we can use two iteractors to scan the elements, the first one is the scanning iterator, and the second one is the end iterator.

When the scanning iterator meets the end iterator, this array is exhausted.

So we can use a list of iterator pairs, for each level:

• if there are new arrays to scan, add its begin and end iterator into the list
• For iterator pairs in the list, visit each of them and add the corresponding elements to the result.
• We add the updated iterator pair into the end of the list if the array is not exhausted.

// OJ: https://leetcode.com/problems/diagonal-traverse-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
    typedef vector<int>::iterator iter;
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& A) {
        vector<int> ans;
        int i = 0, N = A.size();
        list<pair<iter, iter>> q;
        while (i < N || q.size()) {
            if (i < N) {
                q.emplace_front(A[i].begin(), A[i].end());
                ++i;
            }
            int cnt = q.size();
            while (cnt--) {
                auto p = q.front();
                q.pop_front();
                ans.push_back(*p.first);
                p.first++;
                if (p.first != p.second) q.emplace_back(p.first, p.second);
            }
        }
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/diagonal-traverse-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& A) {
        vector<vector<int>> tmp;
        vector<int> ans;
        for (int i = 0; i < A.size(); ++i) {
            for (int j = 0; j < A[i].size(); ++j) {
                if (i + j == tmp.size()) tmp.emplace_back();
                tmp[i + j].push_back(A[i][j]);
            }
        }
        for (auto &row : tmp) {
            for (auto it = rbegin(row); it != rend(row); ++it) {
                ans.push_back(*it);
            }
        }
        return ans;
    }
};