Approach 1
In this approach, we will be using HashMap and ArrayDeque. HashMap is used to store key and value pairs, where values should be unique. ArrayDeque provides a way to apply resizable-array in addition to the implementation of the Deque interface.
In this algorithm, we will be using the inbuilt functions of HashMap.
We will be using an extra array for storing the diagonal order traversal elements.
Code
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Diagonal {
public int[] DiagonalOrder(List<List<Integer>> nums)
{
//diagonal -- element associated with it
Map<Integer, ArrayDeque<Integer>> map= new HashMap<>();
int max= 0, size= 0, index= 0;
//traversing the row in the 2 D array
for(int i= 0; i< nums.size(); i++)
{
//calculating the number of element in the 2D Array
size+= nums.get(i).size();
//traversing inside the row in the 2 D array
for(int j= 0; j< nums.get(i).size(); j++)
{
//diagonal we are currently dealing with
int diagonal= i+j;
//if the diagonal is not present in the HashMap, then creating a entry with that diagonal
map.putIfAbsent(diagonal, new ArrayDeque<Integer>());
//Insertion order is Maintained by ArrayDeque//putting into the Array
map.get(diagonal).addFirst(nums.get(i).get(j));
//calculating the maximum diagonal at every instant
max= Math.max(max, diagonal);
}
}
//resultant array containing the diagonal order traversal elements
int[] res= new int[size];
//every diagonal is associated with number of elements
for(int i= 0; i<= max; i++)
{
while(!map.get(i).isEmpty())
{
//retiring the elements associated with each diagonal, sequentially
res[index]= map.get(i).poll();
//for moving from one index to another index in the resultant Array
index+= 1;
}
}
return res;
}
}
You can also try this code with Online Java Compiler
Analysis of Complexity
Time Complexity: The time complexity of this particular approach will be O(m*n). Where m and n are the sizes of rows and columns, respectively.
Space Complexity: The space complexity will be O(n). An array is needed to store the diagonal array elements.
Approach 2
We will now discuss an efficient approach to solving this particular problem.
We will be using Stacks to make our solution more efficient. Stack is a linear data that follows LIFO(Last In First Out) order, i.e., the most recently added element to be removed first. You can check out more about Stack Data Structure here.
Algorithm
- For numbers on one diagonal sum of the index of the list and the index in the list is the same. This means we know the diagonal of the element when we traverse lists.
- If we swipe from top to bottom from left to right, then elements are traversed in reversed order for each diagonal. This means if we use Stack, then popping from the Stack will give us the correct final order. Another thing - we are traversing diagonals in acs order, so we can add a Stack for every diagonal as we go.
This solution is better than the hashmap approach since if you use hashmap, the number of numbers in the matrix is really large, it will cause the hash collision, and then I see them doing the reverse which causes more time.
Code
public int[] DiagonalOrder(List<List<Integer>> nums) {
int count = 0;
List<Stack<Integer>> list = new ArrayList();
for (int i = 0; i < nums.size(); i++) {
List<Integer> oneList = nums.get(i);
for (int j = 0; j < oneList.size(); j++) {
//this is id of the diagonal
int idx = i + j;
//check if we haven't checked this diagonal before
if (list.size() < idx + 1) {
list.add(new Stack());
}
list.get(idx).push(oneList.get(j));
++count;
}
}
//now traverse the list of stacks to form the final array
int[] res = new int[count];
int p = 0;
for (Stack<Integer> stack : list) {
while(!stack.isEmpty()) {
res[p++] = stack.pop();
}
}
return res;
}
You can also try this code with Online Java Compiler
Analysis of Complexity
Time Complexity: O(n) time as we traverse every element of the list once; we do constant work for each element. Then we again traverse every element once to form the resulting array.
Space Complexity: O(n) space as we need to put every element of the list to a list of stacks.
Frequently Asked Questions
What do you mean by HashMap?
HashMap allows us to store key and value pairs, where keys should be unique. It is like a Hashtable class but not synchronized. It may have one null key and multiple null values.
How does Stack data structure help in coding?
Stack is a linear data structure that performs operations on some order and that order is known as LIFO(Last IN First Out) i.e., the most recently added element is removed first.
What do you mean by ArrayDeque?
ArrayDeques have no capacity restrictions. Null elements are prohibited here and it is likely to be faster than Stack when used as a stack.
Conclusion
In this article, we talked about the traversal of lists in a diagonal manner where the length of all rows can be different. We have implemented in Java language along with their time and space complexities with the help of important data structures.
Recommended Reading:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Keep Coding!!!
24+ registered 
