Jobs

Interviews

Discussions

Diagonal Traverse II

Medium

Asked by:

More companies

43 views

Topics:

Arrays

Given a 2D integer array nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

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

Example 2:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i].length <= 10⁵
1 <= sum(nums[i].length) <= 10⁵
1 <= nums[i][j] <= 10⁵

Try coding it in LeetCode

Diagonal Traverse II

Medium

Asked by:

43 views

Topics:

Arrays

Given a 2D integer array nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

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

Example 2:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i].length <= 10⁵
1 <= sum(nums[i].length) <= 10⁵
1 <= nums[i][j] <= 10⁵

Try coding it in LeetCode

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:

What are the constraints on the dimensions of the input list of lists, specifically the maximum number of rows and the maximum length of each row?
Can the integer values within the lists be negative, zero, or are they guaranteed to be positive?
Is the input list guaranteed to be rectangular (i.e., each inner list has the same length), or can the inner lists have varying lengths?
If the input list `nums` is empty or contains only empty lists, what should the function return: an empty list or should it throw an exception?
Are there any memory constraints I should be aware of, given the potential size of the input?

Brute Force Solution

Approach

We're given a collection of numbers organized like a table that isn't perfectly square. The brute force method means we'll explore all possible diagonal paths through this table, one at a time. We'll examine each number as we go along these paths and construct the final sequence.

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

Start with the top-left number. This is the beginning of our first diagonal.
Now, consider all other potential diagonals. Each diagonal has a starting point.
For each possible diagonal start position, trace the diagonal: Gather the numbers along that diagonal one by one.
As we trace the diagonal, make sure we don't go off the edge of the table.
Once we reach the end of a diagonal, save the list of numbers we collected along that path.
Repeat this process for every possible starting point until we've found all possible diagonals.
Finally, combine all the diagonal sequences we found into a single sequence in the order we visited their starting points.

Code Implementation

def diagonal_traverse_two_brute_force(matrix):
    rows = len(matrix)
    cols = max(len(row) for row in matrix)
    result = []

    # Iterate through all possible starting points.
    for start_row in range(rows):
        diagonal_elements = []
        row_index = start_row
        col_index = 0

        # Traverse the diagonal from the starting point.
        while row_index >= 0 and col_index < cols:
            if col_index < len(matrix[row_index]):
                diagonal_elements.append(matrix[row_index][col_index])
            row_index -= 1
            col_index += 1
        result.extend(diagonal_elements)

    # Iterate through starting columns of the first row.
    for start_col in range(1, cols):
        diagonal_elements = []
        row_index = 0
        col_index = start_col

        # Traverse diagonal. Skip empty cells.
        while row_index < rows and col_index < cols:
            if col_index < len(matrix[row_index]):
                diagonal_elements.append(matrix[row_index][col_index])
            row_index += 1
            col_index += 1
        result.extend(diagonal_elements)

    # Accumulate the diagonal sequences found into a single sequence.
    return result

Big(O) Analysis

Time Complexity

O(n²) – Let n be the total number of elements across all lists. The algorithm iterates through possible diagonal starting positions, which could be up to the number of lists and elements in the first list. For each starting position, the algorithm traces the diagonal until it hits the boundary of the input list of lists. In the worst case, tracing a diagonal can involve visiting a significant portion of the n elements. Since we may need to do this for potentially a number of starting points proportional to n, the time complexity approaches O(n * n), which simplifies to O(n²).

Space Complexity

O(N) – The algorithm accumulates the numbers along each diagonal into a temporary list before appending them to the final result. In the worst-case scenario, where all elements lie on a single long diagonal, this temporary list could hold up to N elements, where N is the total number of elements in the input table. The space to store all the diagonal sequences will also be proportional to N, as each element is stored in exactly one diagonal sequence. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The trick to solving this quickly is realizing that elements on the same diagonal have a constant sum of their row and column positions. We group elements by these sums and then extract them in the right order, ensuring a fast and efficient traversal.

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

First, figure out which diagonal each number belongs to by adding its row and column position together. Numbers on the same diagonal will have the same sum.
Next, group all the numbers that belong to the same diagonal together. So, all numbers with the same row+column sum will be in the same group.
Now that you have the numbers grouped by diagonal, you need to arrange each diagonal's numbers in the correct order. Think about it: within each diagonal, you want to read the numbers from bottom to top.
Finally, go through each diagonal group, one after another, and put the numbers into a single list to get the desired diagonal order.

Code Implementation

def diagonal_traverse_ii(matrix):
    diagonals = {}
    
    # Group elements by their diagonal index (row + col).
    for row_index in range(len(matrix)): 
        for col_index in range(len(matrix[row_index])):
            diagonal_index = row_index + col_index
            if diagonal_index not in diagonals:
                diagonals[diagonal_index] = []
            diagonals[diagonal_index].append(matrix[row_index][col_index])

    result = []
    
    # Iterate through diagonals in ascending order.
    for diagonal_index in sorted(diagonals.keys()):
        # Reverse each diagonal to get correct order
        diagonals_list = diagonals[diagonal_index][::-1]

        # Extend result with the elements from the current diagonal.
        result.extend(diagonals_list)

    return result

Big(O) Analysis

Time Complexity

O(N) – The algorithm iterates through each element of the input list once to calculate the diagonal index (row + column) and add it to the corresponding diagonal group. Creating the diagonal groups involves potentially inserting each element once. Finally, it iterates through the diagonal groups and their elements to construct the result. Since we process each of the N elements in the input list a constant number of times, the overall time complexity is O(N), where N is the total number of elements in the input list.

Space Complexity

O(N) – The solution uses a hash map (or similar data structure) to group elements by the sum of their row and column indices, which corresponds to the diagonal they belong to. In the worst case, all N elements of the input matrix could potentially belong to different diagonals, leading to storing all N elements in the hash map. Therefore, the auxiliary space required for grouping elements is proportional to N. The final list to store the result has the same size as input array, but since we are looking at the auxiliary space, it would be for the hashmap, which dictates the complexity.

Edge Cases

Case	How to Handle
Empty input list `nums`	Return an empty list since there are no elements to traverse.
Empty inner lists within `nums`	Skip over empty inner lists during traversal to avoid errors.
`nums` contains only one row	Iterate directly over the single row and return the elements in order.
`nums` contains only one element	Return a list containing only that single element.
Large input size that could cause memory issues if all elements are added to a single list simultaneously.	The solution should handle large input sizes by processing elements in batches or using an iterator pattern if needed to avoid excessive memory consumption
Input list with extremely different lengths of inner lists.	The algorithm should correctly handle jagged lists, ensuring that out-of-bounds access does not occur by checking boundaries before element access.
Input list containing negative numbers, zeros and large positive numbers	The algorithm should handle negative numbers, zeros, and large positive numbers without issues as they do not affect the logic of diagonal traversal.
Potential integer overflow if row + col index exceeds the maximum integer value	Use a data type with larger capacity if row + col index could cause integer overflow, or consider alternative approach that avoids addition of row and column indices.

Empty input list `nums`

How to Handle:

Return an empty list since there are no elements to traverse.

Empty inner lists within `nums`

How to Handle:

Skip over empty inner lists during traversal to avoid errors.

`nums` contains only one row

How to Handle:

Iterate directly over the single row and return the elements in order.

`nums` contains only one element

How to Handle:

Return a list containing only that single element.

Large input size that could cause memory issues if all elements are added to a single list simultaneously.

How to Handle:

The solution should handle large input sizes by processing elements in batches or using an iterator pattern if needed to avoid excessive memory consumption

Input list with extremely different lengths of inner lists.

How to Handle:

The algorithm should correctly handle jagged lists, ensuring that out-of-bounds access does not occur by checking boundaries before element access.

Input list containing negative numbers, zeros and large positive numbers

How to Handle:

The algorithm should handle negative numbers, zeros, and large positive numbers without issues as they do not affect the logic of diagonal traversal.

Potential integer overflow if row + col index exceeds the maximum integer value

How to Handle:

Use a data type with larger capacity if row + col index could cause integer overflow, or consider alternative approach that avoids addition of row and column indices.

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:

What are the constraints on the dimensions of the input list of lists, specifically the maximum number of rows and the maximum length of each row?
Can the integer values within the lists be negative, zero, or are they guaranteed to be positive?
Is the input list guaranteed to be rectangular (i.e., each inner list has the same length), or can the inner lists have varying lengths?
If the input list `nums` is empty or contains only empty lists, what should the function return: an empty list or should it throw an exception?
Are there any memory constraints I should be aware of, given the potential size of the input?

Brute Force Solution

Approach

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

Start with the top-left number. This is the beginning of our first diagonal.
Now, consider all other potential diagonals. Each diagonal has a starting point.
For each possible diagonal start position, trace the diagonal: Gather the numbers along that diagonal one by one.
As we trace the diagonal, make sure we don't go off the edge of the table.
Once we reach the end of a diagonal, save the list of numbers we collected along that path.
Repeat this process for every possible starting point until we've found all possible diagonals.
Finally, combine all the diagonal sequences we found into a single sequence in the order we visited their starting points.

Code Implementation

def diagonal_traverse_two_brute_force(matrix):
    rows = len(matrix)
    cols = max(len(row) for row in matrix)
    result = []

    # Iterate through all possible starting points.
    for start_row in range(rows):
        diagonal_elements = []
        row_index = start_row
        col_index = 0

        # Traverse the diagonal from the starting point.
        while row_index >= 0 and col_index < cols:
            if col_index < len(matrix[row_index]):
                diagonal_elements.append(matrix[row_index][col_index])
            row_index -= 1
            col_index += 1
        result.extend(diagonal_elements)

    # Iterate through starting columns of the first row.
    for start_col in range(1, cols):
        diagonal_elements = []
        row_index = 0
        col_index = start_col

        # Traverse diagonal. Skip empty cells.
        while row_index < rows and col_index < cols:
            if col_index < len(matrix[row_index]):
                diagonal_elements.append(matrix[row_index][col_index])
            row_index += 1
            col_index += 1
        result.extend(diagonal_elements)

    # Accumulate the diagonal sequences found into a single sequence.
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, figure out which diagonal each number belongs to by adding its row and column position together. Numbers on the same diagonal will have the same sum.
Next, group all the numbers that belong to the same diagonal together. So, all numbers with the same row+column sum will be in the same group.
Now that you have the numbers grouped by diagonal, you need to arrange each diagonal's numbers in the correct order. Think about it: within each diagonal, you want to read the numbers from bottom to top.
Finally, go through each diagonal group, one after another, and put the numbers into a single list to get the desired diagonal order.

Code Implementation

def diagonal_traverse_ii(matrix):
    diagonals = {}
    
    # Group elements by their diagonal index (row + col).
    for row_index in range(len(matrix)): 
        for col_index in range(len(matrix[row_index])):
            diagonal_index = row_index + col_index
            if diagonal_index not in diagonals:
                diagonals[diagonal_index] = []
            diagonals[diagonal_index].append(matrix[row_index][col_index])

    result = []
    
    # Iterate through diagonals in ascending order.
    for diagonal_index in sorted(diagonals.keys()):
        # Reverse each diagonal to get correct order
        diagonals_list = diagonals[diagonal_index][::-1]

        # Extend result with the elements from the current diagonal.
        result.extend(diagonals_list)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input list `nums`	Return an empty list since there are no elements to traverse.
Empty inner lists within `nums`	Skip over empty inner lists during traversal to avoid errors.
`nums` contains only one row	Iterate directly over the single row and return the elements in order.
`nums` contains only one element	Return a list containing only that single element.
Large input size that could cause memory issues if all elements are added to a single list simultaneously.	The solution should handle large input sizes by processing elements in batches or using an iterator pattern if needed to avoid excessive memory consumption
Input list with extremely different lengths of inner lists.	The algorithm should correctly handle jagged lists, ensuring that out-of-bounds access does not occur by checking boundaries before element access.
Input list containing negative numbers, zeros and large positive numbers	The algorithm should handle negative numbers, zeros, and large positive numbers without issues as they do not affect the logic of diagonal traversal.
Potential integer overflow if row + col index exceeds the maximum integer value	Use a data type with larger capacity if row + col index could cause integer overflow, or consider alternative approach that avoids addition of row and column indices.

Empty input list `nums`

How to Handle:

Return an empty list since there are no elements to traverse.

Empty inner lists within `nums`

How to Handle:

Skip over empty inner lists during traversal to avoid errors.

`nums` contains only one row

How to Handle:

Iterate directly over the single row and return the elements in order.

`nums` contains only one element

How to Handle:

Return a list containing only that single element.

Large input size that could cause memory issues if all elements are added to a single list simultaneously.

How to Handle:

The solution should handle large input sizes by processing elements in batches or using an iterator pattern if needed to avoid excessive memory consumption

Input list with extremely different lengths of inner lists.

How to Handle:

The algorithm should correctly handle jagged lists, ensuring that out-of-bounds access does not occur by checking boundaries before element access.

Input list containing negative numbers, zeros and large positive numbers

How to Handle:

The algorithm should handle negative numbers, zeros, and large positive numbers without issues as they do not affect the logic of diagonal traversal.

Potential integer overflow if row + col index exceeds the maximum integer value

How to Handle:

Use a data type with larger capacity if row + col index could cause integer overflow, or consider alternative approach that avoids addition of row and column indices.