Diagonal Traverse II

Problem Description

Given a 2D integer array nums, return all elements of nums in diagonal order as shown in the below images.

Key Insights

• The elements are accessed in a diagonal manner, starting from the top-left corner and moving to the bottom-right.
• Each diagonal can be identified by the sum of its indices (i + j).
• The order of accessing elements in each diagonal is from bottom to top.

Space and Time Complexity

Time Complexity: O(N), where N is the total number of elements in the 2D array nums.
Space Complexity: O(N) for storing the output.

Solution

To solve this problem, we can use a hashmap (dictionary) to group elements by their diagonal index, which is determined by the sum of their row and column indices. After populating the hashmap, we can iterate through the keys in sorted order and collect elements from each diagonal in reverse order (to achieve bottom-to-top traversal).

The algorithm follows these steps:

1. Initialize a hashmap to store lists of elements for each diagonal index.
2. Iterate through each element in the 2D array, adding it to the appropriate list in the hashmap based on its diagonal index.
3. Collect elements from the hashmap in order of their diagonal index, reversing each list to maintain the correct order.

Code Solutions