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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Diagonal Traverse

Number: 498

Difficulty: Medium

Paid? No

Companies: Meta, Walmart Labs, Zoho, Google, TikTok, Amazon, Roblox

Problem Description

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

Key Insights

  • Traverse the matrix diagonally with alternating directions: upward (top-right) and downward (bottom-left).
  • When the traversal reaches a boundary (top, bottom, left, or right), adjust the position and change the direction.
  • Use simulation to process each element exactly once while managing the indices based on the current direction.

Space and Time Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns, as every element is processed once.
Space Complexity: O(m * n) for the output array (excluding the input matrix), while additional space usage remains constant.

Solution

The solution simulates the diagonal traversal using a direction flag (1 for upward and -1 for downward).

  1. Begin at the matrix's top-left corner.
  2. Append the current element to the result.
  3. Depending on the current direction:
    • If moving upward, decrease the row and increase the column.
    • If moving downward, increase the row and decrease the column.
  4. Adjust for boundary hits:
    • When moving upward:
      • If at the last column, increment the row and switch direction.
      • If at the first row, increment the column and switch direction.
    • When moving downward:
      • If at the last row, increment the column and switch direction.
      • If at the first column, increment the row and switch direction. This process continues until all elements are added to the result array.

Code Solutions

def findDiagonalOrder(mat):
    if not mat or not mat[0]:
        return []
    
    m, n = len(mat), len(mat[0])
    result = []
    row, col = 0, 0
    direction = 1  # 1 means upward, -1 means downward

    while len(result) < m * n:
        result.append(mat[row][col])
        if direction == 1:  # moving upward
            if col == n - 1:  # Hit the right boundary
                row += 1
                direction = -1
            elif row == 0:  # Hit the top boundary
                col += 1
                direction = -1
            else:
                row -= 1
                col += 1
        else:  # moving downward
            if row == m - 1:  # Hit the bottom boundary
                col += 1
                direction = 1
            elif col == 0:  # Hit the left boundary
                row += 1
                direction = 1
            else:
                row += 1
                col -= 1
    return result

# Example usage:
print(findDiagonalOrder([[1,2,3],[4,5,6],[7,8,9]]))
← Back to All Questions