Leetcode #1424: Diagonal Traverse II

Link To Problem

Diagonal Traverse II

Key Idea

In a 2D matrix, elements in the same diagonal have same sum of their indices.

So if we have all elements with same sum of their indices together, then it’s just a matter of printing those elements in order.

Leetcode #1424: Diagonal Traverse II - Diagram for visualization - Problem Solving - Coding Interview - Leetcode
Leetcode #1424: Diagonal Traverse II – Diagram for visualization

Algorithm

  1. Insert all elements into an appropriate bucket i.e. nums[i][j] in (i+j)th bucket.
  2. For each bucket starting from 0 to max, print all elements in the bucket.
    Note: Here, diagonals are from bottom to top, but we traversed the input matrix from first row to last row. Hence we need to print the elements in reverse order.

Code

vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
vector<int> answer;
unordered_map<int, vector<int>> m;
int maxKey = 0; // maximum key inserted into the map i.e. max value of i+j indices.
for (int i=0; i<nums.size(); i++) {
for (int j=0; j<nums[i].size(); j++) {
m[i+j].push_back(nums[i][j]); // insert nums[i][j] in bucket (i+j).
maxKey = max(maxKey, i+j); //
}
}
for (int i=0; i<= maxKey; i++) { // Each diagonal starting with sum 0 to sum maxKey.
for (auto x = m[i].rbegin(); x != m[i].rend(); x++) { // print in reverse order.
answer.push_back(*x);
}
}
return answer;
}
view raw Leetcode_1424.cpp hosted with ❤ by GitHub

Is there anything that is still unclear? Let me know in the comments and I can elaborate further.

Don’t forget to like & share the post, and subscribe to the blog to get notifications whenever solution to a new problem is added.

Happy Coding!

Similar Problems

Leetcode #54: Spiral Matrix
Leetcode #498: Diagonal Traverse


Related Posts


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s