# Diagonal Traverse II

Hi Geeks ! Welcome to 100 days of Leetcode challenge.

Day 57 of 100

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. `1 <= nums.length <= 10^5`
2. `1 <= nums[i].length <= 10^5`
3. `1 <= nums[i][j] <= 10^9`
4. There at most `10^5` elements in `nums`.

## Solution

If you use Java, go with HashMap. Here I solved this problem by using Dictionary.

Logic is same, only the syntax looks different from Java.

### C# Program

```public class Solution {
public int[] FindDiagonalOrder(IList<IList<int>> nums) {

Dictionary<int,List<int>> diagonals = new Dictionary<int,List<int>>();

int maxKey = 0, n = 0;

for(int row = nums.Count-1; row >= 0;row--){

for(int col=0; col<nums[row].Count; col++){

int key = row + col;

if(diagonals.ContainsKey(key))
{
}
else
{
}
n++;
maxKey = Math.Max(key,maxKey);
}
}

int[] result = new int[n];
int index = 0;

for(int key = 0; key <= maxKey; key++)
{
if(diagonals.ContainsKey(key)){
List<int> values = diagonals[key];
foreach(int num in values)
result[index++] = num;
}

}
return result;
}
}
```

Time Complexity: O(n)

Space Complexity: O(n)