Jobs

Interviews

Discussions

Spiral Matrix IV

Medium

Asked by:

38 views

Topics:

ArraysLinked Lists

You are given two integers m and n, which represent the dimensions of a matrix.

You are also given the head of a linked list of integers.

Generate an m x n matrix that contains the integers in the linked list presented in spiral order (clockwise), starting from the top-left of the matrix. If there are remaining empty spaces, fill them with -1.

Return the generated matrix.

Example 1:

Input: m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
Output: [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
Explanation: The diagram above shows how the values are printed in the matrix.
Note that the remaining spaces in the matrix are filled with -1.

Example 2:

Input: m = 1, n = 4, head = [0,1,2]
Output: [[0,1,2,-1]]
Explanation: The diagram above shows how the values are printed from left to right in the matrix.
The last space in the matrix is set to -1.

Constraints:

1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
The number of nodes in the list is in the range [1, m * n].
0 <= Node.val <= 1000

Try coding it in LeetCode

Spiral Matrix IV

Medium

Asked by:

38 views

Topics:

ArraysLinked Lists

You are given two integers m and n, which represent the dimensions of a matrix.

You are also given the head of a linked list of integers.

Return the generated matrix.

Example 1:

Input: m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
Output: [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
Explanation: The diagram above shows how the values are printed in the matrix.
Note that the remaining spaces in the matrix are filled with -1.

Example 2:

Input: m = 1, n = 4, head = [0,1,2]
Output: [[0,1,2,-1]]
Explanation: The diagram above shows how the values are printed from left to right in the matrix.
The last space in the matrix is set to -1.

Constraints:

1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
The number of nodes in the list is in the range [1, m * n].
0 <= Node.val <= 1000

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:

Can the input list `head` be empty or null?
Are the dimensions `m` and `n` of the output matrix always positive?
Is the input list `head` guaranteed to have enough elements to fill the entire `m x n` matrix, or should I handle cases where the list is shorter?
What value should I use to fill the matrix cells after exhausting the list, or if the list is empty to begin with?
Should the spiral traversal always start at the top-left corner and proceed in a clockwise direction, or could there be variations?

Brute Force Solution

Approach

We're given a list of numbers and need to arrange them in a spiral pattern inside a rectangle. The brute force way involves trying every possible arrangement by manually walking through the spiral path and placing numbers.

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

Imagine starting at the top-left corner of the rectangle.
Try to fill the first row with numbers from the list, one by one, until we run out of numbers or reach the end of the row.
Then, move to the rightmost column and fill it downwards with remaining numbers, again stopping if we run out of numbers or space.
Next, go to the bottom row and fill it backwards from right to left with remaining numbers.
Finally, move to the leftmost column and fill it upwards with remaining numbers.
Repeat the process, moving inwards layer by layer, until the entire rectangle is filled or we run out of numbers.
If we run out of numbers before filling the entire rectangle, fill the remaining spots with a special value like -1.

Code Implementation

def spiral_matrix_iv(rows, columns, head):
    result_matrix = [([-1] * columns) for _ in range(rows)]
    row_start = 0
    row_end = rows - 1
    column_start = 0
    column_end = columns - 1

    list_node = head

    while row_start <= row_end and column_start <= column_end:
        # Traverse right. Fill the top row.
        for column_index in range(column_start, column_end + 1):
            if list_node:
                result_matrix[row_start][column_index] = list_node.val
                list_node = list_node.next
            else:
                break
        row_start += 1
        if not list_node:
            break

        # Traverse down. Fill the rightmost column.
        for row_index in range(row_start, row_end + 1):
            if list_node:
                result_matrix[row_index][column_end] = list_node.val
                list_node = list_node.next
            else:
                break
        column_end -= 1
        if not list_node:
            break

        # Traverse left. Fill the bottom row.
        if row_start <= row_end:
            for column_index in range(column_end, column_start - 1, -1):
                if list_node:
                    result_matrix[row_end][column_index] = list_node.val
                    list_node = list_node.next
                else:
                    break
        row_end -= 1
        if not list_node:
            break

        # Traverse up. Fill the leftmost column.
        if column_start <= column_end:
            # Prevents overlapping in the center
            for row_index in range(row_end, row_start - 1, -1):
                if list_node:
                    result_matrix[row_start -1][column_start] = list_node.val
                    list_node = list_node.next
                else:
                    break
        column_start += 1

    return result_matrix

Big(O) Analysis

Time Complexity

O(m * n) – The algorithm iterates through the matrix in a spiral fashion, filling each cell with a value from the input list or -1 if the list is exhausted. In the worst-case scenario, the algorithm fills every cell in the m x n matrix. Filling each cell takes constant time. Therefore, the overall time complexity is proportional to the number of cells in the matrix, which is m * n.

Space Complexity

O(m*n) – The dominant space complexity comes from creating the m x n matrix to store the spiral arrangement of numbers. Regardless of the number of elements in the input list, the algorithm needs to allocate space for the output matrix. The space required is directly proportional to the dimensions of the resulting matrix, where m represents the number of rows and n represents the number of columns. Therefore, the auxiliary space complexity is O(m*n).

Optimal Solution

Approach

We need to fill the matrix in a spiral pattern using the values from the given list. The trick is to carefully manage the boundaries of the spiral as we move around the matrix, ensuring we don't go out of bounds or revisit filled cells.

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

Start filling the matrix from the top-left corner, moving right until you hit the boundary.
Then, move downwards, filling the rightmost column until you hit the boundary.
Next, move leftwards, filling the bottom row until you hit the boundary.
After that, move upwards, filling the leftmost column until you hit the boundary.
Repeat these steps, each time moving inwards and adjusting the boundaries, until either all the elements from the list are placed or the entire matrix is filled.
If the list has more elements than the matrix can hold, stop after filling the matrix.
If the list runs out of elements before the matrix is completely filled, fill the remaining cells with -1.

Code Implementation

def spiralMatrixIV(rows, cols, head):
    matrix = [[-1] * cols for _ in range(rows)]
    row_start = 0
    row_end = rows - 1
    col_start = 0
    col_end = cols - 1

    current_node = head

    while current_node:
        # Traverse right
        for col_index in range(col_start, col_end + 1):
            if current_node:
                matrix[row_start][col_index] = current_node.val
                current_node = current_node.next
            else:
                break
        row_start += 1

        if not current_node:
            break

        # Traverse down
        for row_index in range(row_start, row_end + 1):
            if current_node:
                matrix[row_index][col_end] = current_node.val
                current_node = current_node.next
            else:
                break
        col_end -= 1

        if not current_node:
            break

        # Traverse left
        # Important to ensure the loop doesn't run backwards
        for col_index in range(col_end, col_start - 1, -1):
            if current_node:
                matrix[row_end][col_index] = current_node.val
                current_node = current_node.next
            else:
                break
        row_end -= 1

        if not current_node:
            break

        # Traverse up
        # Check to ensure the loops only runs forward.
        for row_index in range(row_end, row_start - 1, -1):
            if current_node:
                matrix[row_index][col_start] = current_node.val
                current_node = current_node.next
            else:
                break
        col_start += 1

        if not current_node:
            break

    return matrix

Big(O) Analysis

Time Complexity

O(m * n) – The algorithm iterates through the matrix of size m x n in a spiral pattern. Each cell in the matrix is visited and filled exactly once. The number of operations is directly proportional to the number of cells in the matrix, which is the product of the number of rows (m) and the number of columns (n). Therefore, the time complexity is O(m * n).

Space Complexity

O(1) – The algorithm fills the matrix in place without using any auxiliary data structures that scale with the input size (dimensions of the matrix or the length of the provided list). While variables are used to track the current position and boundaries, these require a constant amount of extra space. Therefore, the space complexity is O(1) as the auxiliary space does not depend on the input size.

Edge Cases

Case	How to Handle
Null or empty matrix input	Return an empty matrix (or throw an exception, depending on requirements) since no spiral can be formed.
Null or empty list input	Return a matrix filled with zeroes of the correct dimensions, since the list contains no data.
Matrix dimensions are 1xN or Nx1	The spiral algorithm should correctly fill a single row or column matrix sequentially.
List size is smaller than matrix dimensions (m*n)	Fill the matrix until the list is exhausted, and pad the remaining cells with -1.
List contains zero.	Zero is a valid value and should be placed in the matrix normally.
List contains negative numbers.	Negative numbers are valid and should be placed in the matrix normally.
Large matrix dimensions and a very long list: possible memory constraints	Ensure the solution does not use excessive memory by building the matrix incrementally if possible, and be mindful of int overflow.
A square matrix (n x n)	The spiral algorithm should handle square matrices naturally, filling the matrix completely and correctly.

Null or empty matrix input

How to Handle:

Return an empty matrix (or throw an exception, depending on requirements) since no spiral can be formed.

Null or empty list input

How to Handle:

Return a matrix filled with zeroes of the correct dimensions, since the list contains no data.

Matrix dimensions are 1xN or Nx1

How to Handle:

The spiral algorithm should correctly fill a single row or column matrix sequentially.

List size is smaller than matrix dimensions (m*n)

How to Handle:

Fill the matrix until the list is exhausted, and pad the remaining cells with -1.

List contains zero.

How to Handle:

Zero is a valid value and should be placed in the matrix normally.

List contains negative numbers.

How to Handle:

Negative numbers are valid and should be placed in the matrix normally.

Large matrix dimensions and a very long list: possible memory constraints

How to Handle:

Ensure the solution does not use excessive memory by building the matrix incrementally if possible, and be mindful of int overflow.

A square matrix (n x n)

How to Handle:

The spiral algorithm should handle square matrices naturally, filling the matrix completely and correctly.

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 list `head` be empty or null?
Are the dimensions `m` and `n` of the output matrix always positive?
Is the input list `head` guaranteed to have enough elements to fill the entire `m x n` matrix, or should I handle cases where the list is shorter?
What value should I use to fill the matrix cells after exhausting the list, or if the list is empty to begin with?
Should the spiral traversal always start at the top-left corner and proceed in a clockwise direction, or could there be variations?

Brute Force Solution

Approach

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

Imagine starting at the top-left corner of the rectangle.
Try to fill the first row with numbers from the list, one by one, until we run out of numbers or reach the end of the row.
Then, move to the rightmost column and fill it downwards with remaining numbers, again stopping if we run out of numbers or space.
Next, go to the bottom row and fill it backwards from right to left with remaining numbers.
Finally, move to the leftmost column and fill it upwards with remaining numbers.
Repeat the process, moving inwards layer by layer, until the entire rectangle is filled or we run out of numbers.
If we run out of numbers before filling the entire rectangle, fill the remaining spots with a special value like -1.

Code Implementation

def spiral_matrix_iv(rows, columns, head):
    result_matrix = [([-1] * columns) for _ in range(rows)]
    row_start = 0
    row_end = rows - 1
    column_start = 0
    column_end = columns - 1

    list_node = head

    while row_start <= row_end and column_start <= column_end:
        # Traverse right. Fill the top row.
        for column_index in range(column_start, column_end + 1):
            if list_node:
                result_matrix[row_start][column_index] = list_node.val
                list_node = list_node.next
            else:
                break
        row_start += 1
        if not list_node:
            break

        # Traverse down. Fill the rightmost column.
        for row_index in range(row_start, row_end + 1):
            if list_node:
                result_matrix[row_index][column_end] = list_node.val
                list_node = list_node.next
            else:
                break
        column_end -= 1
        if not list_node:
            break

        # Traverse left. Fill the bottom row.
        if row_start <= row_end:
            for column_index in range(column_end, column_start - 1, -1):
                if list_node:
                    result_matrix[row_end][column_index] = list_node.val
                    list_node = list_node.next
                else:
                    break
        row_end -= 1
        if not list_node:
            break

        # Traverse up. Fill the leftmost column.
        if column_start <= column_end:
            # Prevents overlapping in the center
            for row_index in range(row_end, row_start - 1, -1):
                if list_node:
                    result_matrix[row_start -1][column_start] = list_node.val
                    list_node = list_node.next
                else:
                    break
        column_start += 1

    return result_matrix

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start filling the matrix from the top-left corner, moving right until you hit the boundary.
Then, move downwards, filling the rightmost column until you hit the boundary.
Next, move leftwards, filling the bottom row until you hit the boundary.
After that, move upwards, filling the leftmost column until you hit the boundary.
Repeat these steps, each time moving inwards and adjusting the boundaries, until either all the elements from the list are placed or the entire matrix is filled.
If the list has more elements than the matrix can hold, stop after filling the matrix.
If the list runs out of elements before the matrix is completely filled, fill the remaining cells with -1.

Code Implementation

def spiralMatrixIV(rows, cols, head):
    matrix = [[-1] * cols for _ in range(rows)]
    row_start = 0
    row_end = rows - 1
    col_start = 0
    col_end = cols - 1

    current_node = head

    while current_node:
        # Traverse right
        for col_index in range(col_start, col_end + 1):
            if current_node:
                matrix[row_start][col_index] = current_node.val
                current_node = current_node.next
            else:
                break
        row_start += 1

        if not current_node:
            break

        # Traverse down
        for row_index in range(row_start, row_end + 1):
            if current_node:
                matrix[row_index][col_end] = current_node.val
                current_node = current_node.next
            else:
                break
        col_end -= 1

        if not current_node:
            break

        # Traverse left
        # Important to ensure the loop doesn't run backwards
        for col_index in range(col_end, col_start - 1, -1):
            if current_node:
                matrix[row_end][col_index] = current_node.val
                current_node = current_node.next
            else:
                break
        row_end -= 1

        if not current_node:
            break

        # Traverse up
        # Check to ensure the loops only runs forward.
        for row_index in range(row_end, row_start - 1, -1):
            if current_node:
                matrix[row_index][col_start] = current_node.val
                current_node = current_node.next
            else:
                break
        col_start += 1

        if not current_node:
            break

    return matrix

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty matrix input	Return an empty matrix (or throw an exception, depending on requirements) since no spiral can be formed.
Null or empty list input	Return a matrix filled with zeroes of the correct dimensions, since the list contains no data.
Matrix dimensions are 1xN or Nx1	The spiral algorithm should correctly fill a single row or column matrix sequentially.
List size is smaller than matrix dimensions (m*n)	Fill the matrix until the list is exhausted, and pad the remaining cells with -1.
List contains zero.	Zero is a valid value and should be placed in the matrix normally.
List contains negative numbers.	Negative numbers are valid and should be placed in the matrix normally.
Large matrix dimensions and a very long list: possible memory constraints	Ensure the solution does not use excessive memory by building the matrix incrementally if possible, and be mindful of int overflow.
A square matrix (n x n)	The spiral algorithm should handle square matrices naturally, filling the matrix completely and correctly.

Null or empty matrix input

How to Handle:

Return an empty matrix (or throw an exception, depending on requirements) since no spiral can be formed.

Null or empty list input

How to Handle:

Return a matrix filled with zeroes of the correct dimensions, since the list contains no data.

Matrix dimensions are 1xN or Nx1

How to Handle:

The spiral algorithm should correctly fill a single row or column matrix sequentially.

List size is smaller than matrix dimensions (m*n)

How to Handle:

Fill the matrix until the list is exhausted, and pad the remaining cells with -1.

List contains zero.

How to Handle:

Zero is a valid value and should be placed in the matrix normally.

List contains negative numbers.

How to Handle:

Negative numbers are valid and should be placed in the matrix normally.

Large matrix dimensions and a very long list: possible memory constraints

How to Handle:

Ensure the solution does not use excessive memory by building the matrix incrementally if possible, and be mindful of int overflow.

A square matrix (n x n)

How to Handle:

The spiral algorithm should handle square matrices naturally, filling the matrix completely and correctly.