We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Diagonal Traverse

Difficulty: Medium

Problem Description

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

Key Insights

  • The traversal of the matrix follows a diagonal pattern, alternating between moving up and down.
  • The first element of each diagonal can be identified by its starting index, either from the first row or the last column.
  • The direction of traversal changes when reaching the bounds of the matrix (either top or bottom for upward and left or right for downward).

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(1) (excluding the output array)

Solution

The algorithm uses two nested loops to traverse the matrix diagonally. We start from each element in the first row and the last column. Depending on the current diagonal, we either move up (when the diagonal index is even) or down (when the diagonal index is odd). The elements are collected in a result array which is returned at the end.

Code Solutions

def findDiagonalOrder(mat):
    if not mat:
        return []
    
    m, n = len(mat), len(mat[0])
    result = []
    for d in range(m + n - 1):
        if d % 2 == 0:
            # Traverse upwards
            r = min(d, m - 1)
            c = d - r
            while r >= 0 and c < n:
                result.append(mat[r][c])
                r -= 1
                c += 1
        else:
            # Traverse downwards
            c = min(d, n - 1)
            r = d - c
            while c >= 0 and r < m:
                result.append(mat[r][c])
                r += 1
                c -= 1
    return result
← Back to All Questions