Diagonal Traverse - Leetcode Solution

Problem Statement:

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order. Example 1:

Input: mat = [[1,2,3], [4,5,6], [7,8,9]] Output: [1,2,4,7,5,3,6,8,9] Example 2:

Input: mat = [[1,2], [3,4]] Output: [1,2,3,4]

Solution:

Approach:

We can define an order the way that makes sense for the problem, iterate over all the elements of the matrix, and use a data structure to cache the results in the order that we defined.

The order can be defined by the sum of indices i and j. When the sum is even we traverse up to the right, and when it is odd we traverse down to the left. We can reiterate the logic that we saw in the matrix diagonal problem to check if the indices resultant from the traversal belong to the matrix.

Algorithm:

initialise an empty list res to cache the results. initialise a variable rightDiagonal to track the direction of diagonal traversal. initialise two pointers i and j to keep track of the current location on the matrix, starting from the first location. iterate over all the elements of the matrix as long as both pointers i and j are within the range of the matrix dimensions: add the current element to the result list. check if the current diagonal direction is to the right up or left down by checking if the sum of i and j is even or odd respectively. If the current diagonal direction is to the right up, check if the current element is the last column. If so, increment i. Else, increment j. If the current diagonal direction is to the left down, check if the current element is the last row. If so, increment j. Else, increment i. return the resultant list.

Time Complexity:

The time complexity is O(m*n) where 'm' is the number of rows and 'n' is the number of columns, as we have to traverse every element in the matrix.

Space Complexity:

The space complexity is also O(mn) since we need to store all 'mn' elements of the matrix in the resultant list.

Implementation:

Here's the Python code for the solution:

class Solution: def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]: if not matrix: return []

    res = []
    m, n = len(matrix), len(matrix[0])
    rightDiagonal = True
    i, j = 0, 0
    
    while i < m and j < n:
        res.append(matrix[i][j])
        if rightDiagonal:
            if j == n - 1:
                i += 1
            elif i == 0:
                j += 1
            else:
                i -= 1
                j += 1
        else:
            if i == m - 1:
                j += 1
            elif j == 0:
                i += 1
            else:
                i += 1
                j -= 1
        
        rightDiagonal = not rightDiagonal
        
    return res

Explanation: We start by checking if the matrix is empty and return an empty list if that is the case.

We initialise an empty list to cache the results.

We store the number of rows and columns in the matrix in variables m and n, respectively.

We initialise a boolean variable rightDiagonal to True to indicate that the first diagonal direction is to the right up.

We initialise two variables i and j to keep track of the current row and column we are at, starting from the first location.

We keep iterating over the elements of the matrix until both i and j pointers have reached the end of the matrix.

We add the current element matrix[i][j] to the resultant list res.

We check the current diagonal direction by checking if the rightDiagonal variable is True or False. If it is True, we check if the current element is at the last column by checking if the j pointer is equal to n - 1. If that is the case, we can move to the next row by incrementing i by 1. If the current element is not at the last column, we check if the current element is at the first row by checking if the i pointer is equal to 0. If that is the case, we can move to the next column by incrementing j by 1. If neither of those conditions apply, we are still traversing in the current diagonal direction, so we decrement i by 1 to move up and increment j by 1 to move right.

If the rightDiagonal variable is False, we check if the current element is at the last row by checking if the i pointer is equal to m - 1. If that is the case, we can move to the next column by incrementing j by 1. If the current element is not at the last row, we check if the current element is at the first column by checking if the j pointer is equal to 0. If that is the case, we can move to the next row by incrementing i by 1. If neither of those conditions apply, we are still traversing in the current diagonal direction, so we increment i by 1 to move down and decrement j by 1 to move left.

We update the value of rightDiagonal to its opposite value as we switch diagonals after every element we traverse.

We return the resultant list res containing all the elements of the matrix traversed diagonally.

1