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

image

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))
                {
                    diagonals[key].Add(nums[row][col]);
                }
                else
                {
                    diagonals.Add(key,new List<int>(){nums[row][col]});    
                }
                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)

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