algoadvance

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

Example:

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]

Clarifying Questions

• Can the matrix mat be empty? If so, should we return an empty list?
• What are the constraints on the sizes of m and n?
• Are all elements of the matrix integers?

Based on typical problem constraints:

• The matrix will have at least one element.
• Constraints typically range from 1 <= m, n <= 10^4.
• Matrix elements are usually within the range of valid integers.

Strategy

The key observation here is that the traversal pattern alternates between moving diagonally up-right and diagonally down-left. We’ll use the following approach:

1. Start from the top-left corner of the matrix.
2. Use a direction flag to switch between upwards and downwards diagonal movements.
3. If going up-right, move from (i, j) to (i-1, j+1).
4. If going down-left, move from (i, j) to (i+1, j-1).
5. Handle boundary conditions to:
   • Switch direction when hitting the matrix boundary.
   • Ensure starting from the proper new position after hitting boundaries.
6. Continue until all elements have been visited.

Code

Here is the Python solution implementing the above strategy:

def findDiagonalOrder(mat):
    if not mat or not mat[0]:
        return []

    m, n = len(mat), len(mat[0])
    result = []

    # Initialize the starting position
    i, j = 0, 0
    direction = 1  # 1 means moving up-right; -1 means moving down-left

    while len(result) < m * n:
        result.append(mat[i][j])
        
        if direction == 1:  # Moving up-right
            if j == n - 1:  # Hit the right boundary
                i += 1
                direction = -1
            elif i == 0:  # Hit the top boundary
                j += 1
                direction = -1
            else:  # Normal move
                i -= 1
                j += 1
        else:  # Moving down-left
            if i == m - 1:  # Hit the bottom boundary
                j += 1
                direction = 1
            elif j == 0:  # Hit the left boundary
                i += 1
                direction = 1
            else:  # Normal move
                i += 1
                j -= 1

    return result

# Test the solution with the provided examples
print(findDiagonalOrder([[1,2,3],[4,5,6],[7,8,9]]))  # Output: [1,2,4,7,5,3,6,8,9]
print(findDiagonalOrder([[1,2],[3,4]]))              # Output: [1,2,3,4]

Time Complexity

The time complexity of this solution is O(m * n), where m is the number of rows and n is the number of columns in the matrix. This is optimal because we need to visit each element exactly once.

The space complexity is O(1) additional space, ignoring the space required to store the result, which is O(m * n).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?