Jobs

Interviews

Discussions

Diagonal Traverse

Medium

Diagonal Traverse of a Matrix

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]

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 10^4
1 <= m * n <= 10^4
-10^5 <= mat[i][j] <= 10^5

Can you implement a function to efficiently traverse the matrix diagonally and return the elements in the specified order?

Diagonal Traverse

Medium

Diagonal Traverse of a Matrix

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]

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 10^4
1 <= m * n <= 10^4
-10^5 <= mat[i][j] <= 10^5

Can you implement a function to efficiently traverse the matrix diagonally and return the elements in the specified order?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input matrix be empty or contain null/empty rows?
What are the possible ranges for the dimensions of the matrix (number of rows and columns)?
What data type will the elements in the matrix be (e.g., integers, floats)? Are negative values possible?
If the input matrix is not square (i.e., number of rows != number of columns), how should the traversal be handled?
In what order should the diagonals be traversed (e.g., starting from the top-left or bottom-left corner)? Is there a preference for up-right or down-left traversal within each diagonal?

Brute Force Solution

Approach

Imagine you're walking through a grid, moving diagonally up and right, then diagonally down and left, and so on. The brute force approach is to simply explore every single possible diagonal path through the grid.

Here's how the algorithm would work step-by-step:

Start at the very beginning, the top left corner of the grid.
Explore the first possible diagonal path, going up and to the right until you hit the edge of the grid.
Once you can't go any further, start a new diagonal path by either moving down from your current spot or moving to the right depending on where you hit the edge.
Keep exploring every possible diagonal path, making sure you cover every element in the grid.
Put all of the elements you encounter along these diagonal paths in a sequence as you find them.
The final sequence represents the elements visited diagonally through the grid in the specific order you explored.

Code Implementation

def diagonal_traverse_brute_force(matrix):
    if not matrix:
        return []

    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])
    result = []
    row = 0
    column = 0
    up = True

    for _ in range(number_of_rows * number_of_columns):
        result.append(matrix[row][column])

        if up:
            next_row = row - 1
            next_column = column + 1

            if next_row < 0 and next_column < number_of_columns:
                # We hit the top edge
                row = 0
                column = next_column
                up = False

            elif next_column == number_of_columns:
                # We hit the right edge
                row = row + 1
                column = number_of_columns - 1
                up = False

            else:
                row = next_row
                column = next_column

        else:
            next_row = row + 1
            next_column = column - 1

            if next_column < 0 and next_row < number_of_rows:
                # We hit the left edge
                row = next_row
                column = 0
                up = True

            elif next_row == number_of_rows:
                # We hit the bottom edge
                row = number_of_rows - 1
                column = column + 1
                up = True

            else:
                row = next_row
                column = next_column

    return result

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through all the elements of the m x n matrix. Each element is visited exactly once as we traverse the diagonals. Therefore, the time complexity is directly proportional to the total number of elements in the matrix, which is m*n, where m is the number of rows and n is the number of columns. Thus, the time complexity is O(m*n).

Space Complexity

O(1) – The plain English explanation focuses on traversing the input grid and doesn't explicitly mention creating any auxiliary data structures like temporary lists or hash maps to store intermediate results or track visited locations. It only describes movement within the existing grid. Therefore, the space complexity is dominated by a few index variables necessary for the traversal, which takes constant space regardless of the input grid's dimensions (N), where N would represent the total number of elements in the grid. This leads to a space complexity of O(1).

Optimal Solution

Approach

The goal is to walk through a grid in a specific diagonal pattern. The clever trick is to realize the direction changes predictably and we can manage it systematically, avoiding complicated calculations.

Here's how the algorithm would work step-by-step:

Start at the top-left corner of the grid.
Go diagonally upwards to the right as far as you can until you hit an edge (either the top or the right).
When you hit the top edge, move one step down.
When you hit the right edge, move one step left.
Switch directions and go diagonally downwards to the left as far as you can until you hit an edge (either the bottom or the left).
When you hit the bottom edge, move one step to the right.
When you hit the left edge, move one step down.
Repeat the process of alternating diagonal directions until you have visited every spot in the grid.

Code Implementation

def diagonal_traverse(matrix):
    if not matrix or not matrix[0]:
        return []

    rows = len(matrix)
    columns = len(matrix[0])
    result = []
    row_index = 0
    column_index = 0
    up = True

    for _ in range(rows * columns):
        result.append(matrix[row_index][column_index])

        if up:
            new_row_index = row_index - 1
            new_column_index = column_index + 1

            if new_row_index < 0 and new_column_index < columns:
                # Hit the top edge, move right
                row_index = 0
                column_index = new_column_index
                up = False

            elif new_column_index >= columns:
                # Hit the right edge, move down
                row_index = row_index + 1
                column_index = columns - 1
                up = False

            else:
                row_index = new_row_index
                column_index = new_column_index

        else:
            new_row_index = row_index + 1
            new_column_index = column_index - 1

            if new_column_index < 0 and new_row_index < rows:
                # Hit the left edge, move down
                column_index = 0
                row_index = new_row_index
                up = True

            elif new_row_index >= rows:
                # Hit the bottom edge, move right
                row_index = rows - 1
                column_index = column_index + 1
                up = True

            else:
                row_index = new_row_index
                column_index = new_column_index

    return result

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each element of the m x n matrix exactly once. Although the movement is diagonal, the key point is that every cell is visited. The direction changes and edge checks do not significantly increase the overall time complexity because they are performed at each cell. Therefore, the time complexity is directly proportional to the total number of elements in the matrix, which is m*n.

Space Complexity

O(1) – The algorithm described operates directly on the input grid without creating any auxiliary data structures like lists, arrays, or hash maps to store intermediate results or track visited cells. It only uses a few variables to maintain the current position (row, col) and direction of traversal. Therefore, the amount of extra memory used is constant and independent of the grid size (N), resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Null or empty matrix	Return an empty list immediately as there's nothing to traverse.
Matrix with only one row or one column	Iterate through the single row or column and add the elements to the result list.
Square matrix with large dimensions (e.g., 1000x1000)	Ensure the algorithm's time and space complexity allows it to handle large inputs efficiently (O(m*n)).
Rectangular matrix where rows >> cols or cols >> rows	The solution should correctly handle different row and column lengths, adjusting the diagonal traversal accordingly.
Matrix contains negative numbers	The algorithm should handle negative numbers without any special logic or error; they are just data.
Matrix contains zero	The algorithm should handle zero values without any special logic; they are just data.
Input matrix contains very large integers that could cause an overflow during intermediate calculations (sum of indices)	Use appropriate data types (e.g., long) for intermediate calculations or take precautions to avoid overflow if the sum of indices exceeds the integer limit.
The input matrix contains duplicate numbers at different positions.	The algorithm should correctly traverse and include all numbers, even if they are duplicates.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input matrix be empty or contain null/empty rows?
What are the possible ranges for the dimensions of the matrix (number of rows and columns)?
What data type will the elements in the matrix be (e.g., integers, floats)? Are negative values possible?
If the input matrix is not square (i.e., number of rows != number of columns), how should the traversal be handled?
In what order should the diagonals be traversed (e.g., starting from the top-left or bottom-left corner)? Is there a preference for up-right or down-left traversal within each diagonal?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very beginning, the top left corner of the grid.
Explore the first possible diagonal path, going up and to the right until you hit the edge of the grid.
Once you can't go any further, start a new diagonal path by either moving down from your current spot or moving to the right depending on where you hit the edge.
Keep exploring every possible diagonal path, making sure you cover every element in the grid.
Put all of the elements you encounter along these diagonal paths in a sequence as you find them.
The final sequence represents the elements visited diagonally through the grid in the specific order you explored.

Code Implementation

def diagonal_traverse_brute_force(matrix):
    if not matrix:
        return []

    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])
    result = []
    row = 0
    column = 0
    up = True

    for _ in range(number_of_rows * number_of_columns):
        result.append(matrix[row][column])

        if up:
            next_row = row - 1
            next_column = column + 1

            if next_row < 0 and next_column < number_of_columns:
                # We hit the top edge
                row = 0
                column = next_column
                up = False

            elif next_column == number_of_columns:
                # We hit the right edge
                row = row + 1
                column = number_of_columns - 1
                up = False

            else:
                row = next_row
                column = next_column

        else:
            next_row = row + 1
            next_column = column - 1

            if next_column < 0 and next_row < number_of_rows:
                # We hit the left edge
                row = next_row
                column = 0
                up = True

            elif next_row == number_of_rows:
                # We hit the bottom edge
                row = number_of_rows - 1
                column = column + 1
                up = True

            else:
                row = next_row
                column = next_column

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the top-left corner of the grid.
Go diagonally upwards to the right as far as you can until you hit an edge (either the top or the right).
When you hit the top edge, move one step down.
When you hit the right edge, move one step left.
Switch directions and go diagonally downwards to the left as far as you can until you hit an edge (either the bottom or the left).
When you hit the bottom edge, move one step to the right.
When you hit the left edge, move one step down.
Repeat the process of alternating diagonal directions until you have visited every spot in the grid.

Code Implementation

def diagonal_traverse(matrix):
    if not matrix or not matrix[0]:
        return []

    rows = len(matrix)
    columns = len(matrix[0])
    result = []
    row_index = 0
    column_index = 0
    up = True

    for _ in range(rows * columns):
        result.append(matrix[row_index][column_index])

        if up:
            new_row_index = row_index - 1
            new_column_index = column_index + 1

            if new_row_index < 0 and new_column_index < columns:
                # Hit the top edge, move right
                row_index = 0
                column_index = new_column_index
                up = False

            elif new_column_index >= columns:
                # Hit the right edge, move down
                row_index = row_index + 1
                column_index = columns - 1
                up = False

            else:
                row_index = new_row_index
                column_index = new_column_index

        else:
            new_row_index = row_index + 1
            new_column_index = column_index - 1

            if new_column_index < 0 and new_row_index < rows:
                # Hit the left edge, move down
                column_index = 0
                row_index = new_row_index
                up = True

            elif new_row_index >= rows:
                # Hit the bottom edge, move right
                row_index = rows - 1
                column_index = column_index + 1
                up = True

            else:
                row_index = new_row_index
                column_index = new_column_index

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty matrix	Return an empty list immediately as there's nothing to traverse.
Matrix with only one row or one column	Iterate through the single row or column and add the elements to the result list.
Square matrix with large dimensions (e.g., 1000x1000)	Ensure the algorithm's time and space complexity allows it to handle large inputs efficiently (O(m*n)).
Rectangular matrix where rows >> cols or cols >> rows	The solution should correctly handle different row and column lengths, adjusting the diagonal traversal accordingly.
Matrix contains negative numbers	The algorithm should handle negative numbers without any special logic or error; they are just data.
Matrix contains zero	The algorithm should handle zero values without any special logic; they are just data.
Input matrix contains very large integers that could cause an overflow during intermediate calculations (sum of indices)	Use appropriate data types (e.g., long) for intermediate calculations or take precautions to avoid overflow if the sum of indices exceeds the integer limit.
The input matrix contains duplicate numbers at different positions.	The algorithm should correctly traverse and include all numbers, even if they are duplicates.