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 innums
.
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
andend
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;
}
}