Problem Statement:

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]] Output: [1,3,2,5,4,6]

Solution:

Approach #1: Brute Force (Accepted Solution) The first approach that comes to our mind is to traverse the matrix just like a 2-D array but in the diagonal fashion as shown in the below image:

Thus for each diagonal we can find the elements that comes under it and we can store them in a list as we keep iterating over all the diagonals.

Algorithm:

1. Initialize an empty list to store the elements
2. Loop over each diagonal a. If the index of the diagonal is even, append the diagonal elements in the reverse order to our list b. If the index of the diagonal is odd, append the diagonal elements in the forward order to our list
3. Return the list

Pseudo-Code

def traverseDiagonal(nums): res = [] for i in range(len(nums)): for j in range(len(nums[i])): # case 1: if the index is even if (i + j) % 2 == 0: res = [nums[row][i - row] for row in range(min(i, len(nums)-1), max(-1, i-len(nums)), -1)] # case 2: if the index is odd else: res = [nums[row][i - row] for row in range(max(0, i-len(nums)+1), min(i+1, len(nums)))] return res

time complexity: O(N^2), space complexity: O(N)

The above solution has a time complexity of O(N^2) and a space complexity of O(N), where N is the total number of elements in the matrix.

Test Cases:

Input: nums = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,4,2,7,5,3,8,6,9] Explanation: The elements of the matrix in diagonal order are [1], [4,2], [7,5,3], [8,6], [9]. Thus we return [1,4,2,7,5,3,8,6,9]

Input: nums = [[1,2],[3,4],[5,6]] Output: [1,3,2,5,4,6] Explanation: The elements of the matrix in diagonal order are [1], [3,2], [5,4], [6]. Thus we return [1,3,2,5,4,6].

1