Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 22

Description

Diagonal Traverse II

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

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
  using vii = vector<int>::iterator;
public:
  vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
    int maxTraverse = 0;
    for(int i = 0; i < nums.size(); ++i) {
      maxTraverse = max<int>(maxTraverse, nums[i].size() + i);
    }

    vector<int> answer;
    queue<pair<vii, vii>> q;
    q.push({nums[0].begin(), nums[0].end()});
    for(int i = 0; i < maxTraverse; ++i) {
      int sz = q.size();
      if(i + 1 < nums.size()) {
        q.push({nums[i + 1].begin(), nums[i + 1].end()});
      }
      for(int _ = 0; _ < sz; ++_) {
        auto [it, eit] = q.front();
        q.pop();
        answer.push_back(*it);
        // cout << i << ' ' << _ << ' ' << *it << endl;
        ++it;
        if(it != eit) q.push({it, eit});
      }
    } 
    return answer;
  }
};

// Accepted
// 56/56 cases passed (108 ms)
// Your runtime beats 96.79 % of cpp submissions
// Your memory usage beats 83.33 % of cpp submissions (70.1 MB)