Formatted question description: https://leetcode.ca/all/1424.html

1424. Diagonal Traverse II (Medium)

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.

Related Topics:
Array, Sort

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/

// 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/

// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& A) {
        unordered_map<int, vector<int>> m;
        int N = A.size(), maxKey = 0, cnt = 0;
        for (int i = N - 1; i >= 0; --i) {
            int M = A[i].size();
            cnt += M;
            for (int j = M - 1; j >= 0; --j) {
                m[i + j].push_back(A[i][j]);
                maxKey = max(maxKey, i + j);
            }
        }
        vector<int> ans;
        ans.reserve(cnt);
        for (int i = 0; i <= maxKey; ++i) {
            for (int n : m[i]) ans.push_back(n);
        }
        return ans;
    }
};

Java

class Solution {
    public int[] findDiagonalOrder(List<List<Integer>> nums) {
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] position1, int[] position2) {
                int sum1 = position1[0] + position1[1], sum2 = position2[0] + position2[1];
                if (sum1 != sum2)
                    return sum1 - sum2;
                else
                    return position2[0] - position1[0];
            }
        });
        int rows = nums.size();
        for (int i = 0; i < rows; i++) {
            int columns = nums.get(i).size();
            for (int j = 0; j < columns; j++)
                priorityQueue.offer(new int[]{i, j});
        }
        int size = priorityQueue.size();
        int[] orderArray = new int[size];
        for (int i = 0; i < size; i++) {
            int[] position = priorityQueue.poll();
            int row = position[0], column = position[1];
            orderArray[i] = nums.get(row).get(column);
        }
        return orderArray;
    }
}

All Problems

All Solutions