Jobs

Interviews

Discussions

Spiral Matrix

Medium

Nvidia

0 views

Topics:

Arrays

Given an m x n matrix, return all elements of the matrix in spiral order.

For example:

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

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Consider the following constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

How would you approach this problem? What are the edge cases that need consideration?

Spiral Matrix

Medium

Nvidia

0 views

Topics:

Arrays

Given an m x n matrix, return all elements of the matrix in spiral order.

For example:

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

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Consider the following constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

How would you approach this problem? What are the edge cases that need consideration?

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 matrix be empty, or can either the number of rows or the number of columns be zero?
What is the range of integer values within the matrix? Should I be concerned about potential integer overflow?
Is the input matrix guaranteed to be rectangular (i.e., each row has the same number of columns)?
In the case of a non-square matrix, which direction should the spiral traversal prioritize when a 'corner' is reached?
What should be returned if the input matrix is null?

Brute Force Solution

Approach

Imagine walking around the edge of a square, then spiraling inward. The brute force approach is to meticulously trace that path, step-by-step, element-by-element. We simulate the process of traversing the matrix in a spiral manner.

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

Start at the top-left corner of the matrix.
Move right, adding each element you encounter to your spiral path until you reach the end of the current row.
Move down, adding each element to the path until you reach the end of the current column.
Move left, adding each element to the path until you reach the beginning of the current row.
Move up, adding each element to the path until you reach the beginning of the current column.
Repeat these steps, moving one layer inward each time, until you have visited every element in the matrix.

Code Implementation

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

    result = []
    start_row = 0
    end_row = len(matrix) - 1
    start_column = 0
    end_column = len(matrix[0]) - 1

    while start_row <= end_row and start_column <= end_column:
        # Traverse right
        for column_index in range(start_column, end_column + 1):
            result.append(matrix[start_row][column_index])

        start_row += 1

        # Traverse down
        for row_index in range(start_row, end_row + 1):
            result.append(matrix[row_index][end_column])

        end_column -= 1

        # Need this check to avoid duplicate rows
        if start_row <= end_row:
            for column_index in range(end_column, start_column - 1, -1):
                result.append(matrix[end_row][column_index])

            end_row -= 1

        # Need this check to avoid duplicate columns
        if start_column <= end_column:
            for row_index in range(end_row, start_row - 1, -1):
                result.append(matrix[row_index][start_column])

            start_column += 1

    return result

Big(O) Analysis

Time Complexity

O(m * n) – The algorithm visits each element in the m x n matrix exactly once. While the traversal is performed in a spiral pattern, the fundamental operation is accessing and adding each element to the result. The number of elements visited 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. Therefore, the time complexity is O(m * n).

Space Complexity

O(1) – The provided algorithm primarily manipulates the input matrix in place. The steps outline a traversal pattern without explicitly mentioning the creation of any new data structures to store visited elements or the spiral path itself. It uses a constant number of variables (e.g., to keep track of current row, column, and boundaries) that are independent of the input matrix size N (where N is the total number of elements in the matrix). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The most efficient way to traverse a matrix in a spiral is to think of it as peeling layers. We repeatedly trace the outer boundaries, shrinking the matrix inwards with each iteration until everything is covered.

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

Imagine tracing the outer rectangle of the matrix: go right along the top row, then down along the rightmost column, then left along the bottom row, and finally up along the leftmost column.
After completing one full cycle of the outer rectangle, mentally remove that outer layer. Now you're left with a smaller rectangle inside.
Repeat the tracing process on this inner rectangle, going right, down, left, and up again.
Keep repeating this process of tracing the outermost layer and then shrinking the problem size until there are no more layers left to trace.

Code Implementation

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

    result = []
    top_row = 0
    bottom_row = len(matrix) - 1
    left_column = 0
    right_column = len(matrix[0]) - 1

    while top_row <= bottom_row and left_column <= right_column:
        # Traverse top row from left to right
        for i in range(left_column, right_column + 1):
            result.append(matrix[top_row][i])
        top_row += 1

        # Traverse right column from top to bottom
        for i in range(top_row, bottom_row + 1):
            result.append(matrix[i][right_column])
        right_column -= 1

        # Need to check if there is a row or column left
        if top_row <= bottom_row:
            # Traverse bottom row from right to left
            for i in range(right_column, left_column - 1, -1):
                result.append(matrix[bottom_row][i])
            bottom_row -= 1

        # Need to check if there is a row or column left
        if left_column <= right_column:
            # Traverse left column from bottom to top
            for i in range(bottom_row, top_row - 1, -1):
                result.append(matrix[i][left_column])
            left_column += 1

    return result

def solve():
    matrix1 = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]
    ]
    print(spiral_matrix(matrix1))

    matrix2 = [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12]
    ]
    print(spiral_matrix(matrix2))

    matrix3 = [
        [1, 2],
        [3, 4]
    ]
    print(spiral_matrix(matrix3))

if __name__ == "__main__":
    solve()

Big(O) Analysis

Time Complexity

O(m * n) – The algorithm processes the matrix by peeling off layers until all elements are visited. In the worst case, every element in the matrix is visited exactly once. If the matrix dimensions are m rows and n columns, the algorithm visits m * n elements. Therefore, the time complexity is directly proportional to the total number of elements in the matrix, resulting in O(m * n).

Space Complexity

O(1) – The provided algorithm traverses the matrix in place, modifying only the boundaries for iteration. It doesn't create any auxiliary data structures like lists, sets, or maps to store intermediate results or visited elements. The space used is limited to a few integer variables to track the current boundaries or indices of the matrix, which remains constant irrespective of the input matrix's dimensions (N). Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or Empty Matrix	Return an empty list immediately if the input matrix is null or has zero rows or columns.
Single Row Matrix	Iterate through the single row from left to right and append each element to the result list.
Single Column Matrix	Iterate through the single column from top to bottom and append each element to the result list.
Square Matrix (n x n)	The algorithm should correctly handle square matrices as a general case of rectangular matrices.
Rectangular Matrix (m x n, m != n)	The algorithm needs to adjust the boundaries correctly to avoid going out of bounds when rows and columns are different.
Matrix with all identical elements	The algorithm should correctly traverse the matrix regardless of the values of the elements.
Large Matrix (performance)	The iterative boundary shrinking approach should have a time complexity of O(m*n) and thus should scale linearly with input size, without excessive memory usage.
Matrix with negative numbers, zeros, and large positive numbers	The algorithm should work correctly regardless of the range or sign of the matrix elements, as we only care about the indices and not the values themselves.

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 matrix be empty, or can either the number of rows or the number of columns be zero?
What is the range of integer values within the matrix? Should I be concerned about potential integer overflow?
Is the input matrix guaranteed to be rectangular (i.e., each row has the same number of columns)?
In the case of a non-square matrix, which direction should the spiral traversal prioritize when a 'corner' is reached?
What should be returned if the input matrix is null?

Brute Force Solution

Approach

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

Start at the top-left corner of the matrix.
Move right, adding each element you encounter to your spiral path until you reach the end of the current row.
Move down, adding each element to the path until you reach the end of the current column.
Move left, adding each element to the path until you reach the beginning of the current row.
Move up, adding each element to the path until you reach the beginning of the current column.
Repeat these steps, moving one layer inward each time, until you have visited every element in the matrix.

Code Implementation

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

    result = []
    start_row = 0
    end_row = len(matrix) - 1
    start_column = 0
    end_column = len(matrix[0]) - 1

    while start_row <= end_row and start_column <= end_column:
        # Traverse right
        for column_index in range(start_column, end_column + 1):
            result.append(matrix[start_row][column_index])

        start_row += 1

        # Traverse down
        for row_index in range(start_row, end_row + 1):
            result.append(matrix[row_index][end_column])

        end_column -= 1

        # Need this check to avoid duplicate rows
        if start_row <= end_row:
            for column_index in range(end_column, start_column - 1, -1):
                result.append(matrix[end_row][column_index])

            end_row -= 1

        # Need this check to avoid duplicate columns
        if start_column <= end_column:
            for row_index in range(end_row, start_row - 1, -1):
                result.append(matrix[row_index][start_column])

            start_column += 1

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine tracing the outer rectangle of the matrix: go right along the top row, then down along the rightmost column, then left along the bottom row, and finally up along the leftmost column.
After completing one full cycle of the outer rectangle, mentally remove that outer layer. Now you're left with a smaller rectangle inside.
Repeat the tracing process on this inner rectangle, going right, down, left, and up again.
Keep repeating this process of tracing the outermost layer and then shrinking the problem size until there are no more layers left to trace.

Code Implementation

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

    result = []
    top_row = 0
    bottom_row = len(matrix) - 1
    left_column = 0
    right_column = len(matrix[0]) - 1

    while top_row <= bottom_row and left_column <= right_column:
        # Traverse top row from left to right
        for i in range(left_column, right_column + 1):
            result.append(matrix[top_row][i])
        top_row += 1

        # Traverse right column from top to bottom
        for i in range(top_row, bottom_row + 1):
            result.append(matrix[i][right_column])
        right_column -= 1

        # Need to check if there is a row or column left
        if top_row <= bottom_row:
            # Traverse bottom row from right to left
            for i in range(right_column, left_column - 1, -1):
                result.append(matrix[bottom_row][i])
            bottom_row -= 1

        # Need to check if there is a row or column left
        if left_column <= right_column:
            # Traverse left column from bottom to top
            for i in range(bottom_row, top_row - 1, -1):
                result.append(matrix[i][left_column])
            left_column += 1

    return result

def solve():
    matrix1 = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]
    ]
    print(spiral_matrix(matrix1))

    matrix2 = [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12]
    ]
    print(spiral_matrix(matrix2))

    matrix3 = [
        [1, 2],
        [3, 4]
    ]
    print(spiral_matrix(matrix3))

if __name__ == "__main__":
    solve()

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or Empty Matrix	Return an empty list immediately if the input matrix is null or has zero rows or columns.
Single Row Matrix	Iterate through the single row from left to right and append each element to the result list.
Single Column Matrix	Iterate through the single column from top to bottom and append each element to the result list.
Square Matrix (n x n)	The algorithm should correctly handle square matrices as a general case of rectangular matrices.
Rectangular Matrix (m x n, m != n)	The algorithm needs to adjust the boundaries correctly to avoid going out of bounds when rows and columns are different.
Matrix with all identical elements	The algorithm should correctly traverse the matrix regardless of the values of the elements.
Large Matrix (performance)	The iterative boundary shrinking approach should have a time complexity of O(m*n) and thus should scale linearly with input size, without excessive memory usage.
Matrix with negative numbers, zeros, and large positive numbers	The algorithm should work correctly regardless of the range or sign of the matrix elements, as we only care about the indices and not the values themselves.