Matrix Spiral Traversal

Write a function spiralOrder that takes a 2D array (matrix) of integers and returns a list of elements in spiral order. Starting from the top left corner of the matrix, move right, then down, then left, and then up, continuing this pattern until all elements are traversed.

Constraints

  • The matrix will have at least 1 row and 1 column and at most 10 rows and 10 columns.
  • Each element in the matrix is an integer.

Examples

Input: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
Explanation: The elements are traversed in a spiral order starting from the top left (1) and moving right, down, left, and up.

Input: [[1, 2], [3, 4]]
Output: [1, 2, 4, 3]
Explanation: Starting from 1, move right to 2, then down to 4, and finally left to 3.

Tips

  • Consider using four loops for each direction of the spiral (right, down, left, up) and keep track of the boundaries of the matrix.
  • Update the boundaries after completing a row or a column traversal to avoid duplicating elements.
  • This problem requires careful handling of the indices and the conditions for changing direction.

Solution

What’s the Exact Matrix Spiral Traversal Problem?

The problem is to traverse a 2D matrix (array of arrays) in a spiral order, starting from the top left corner and moving right, then down, left, and up, repeating this cycle until all elements are covered.

Steps to Understand the Matrix Spiral Traversal Problem:

  • Visualize moving through the matrix in a spiral pattern.
  • Understand that you need to change direction when you reach the end of a row or column or when you encounter a previously traversed element.
  • The challenge lies in keeping track of which elements have been traversed and changing directions accordingly.

Examples

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

Input: [[1, 2], [3, 4]]
Output: [1, 2, 4, 3]

What Your Function Should Do?

The function spiralOrder should accept a 2D matrix and return a list of its elements in spiral order.

How to Solve the Matrix Spiral Traversal Problem?

  • Use four pointers to maintain the bounds of traversal: top, bottom, left, and right.
  • Traverse from left to right, top to bottom, right to left, and bottom to top.
  • After completing a row or a column, adjust the respective boundaries.
  • Continue the process until all elements are traversed.

Example Code Solution

def spiralOrder(matrix):
    result = []
    while matrix:
        result += matrix.pop(0)
        matrix = list(zip(*matrix))[::-1]
    return result

Example Usage

print(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))  # Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
print(spiralOrder([[1, 2], [3, 4]]))                   # Output: [1, 2, 4, 3]

How this Code Works?

  • The function iteratively removes the first row of the matrix and appends it to the result.
  • It then rotates the remaining matrix counter-clockwise (transposing and then reversing each row).
  • This process effectively simulates the spiral traversal, as each removal of the first row corresponds to a traversal in a different direction.

Time Complexity

The time complexity of this solution is O(n), where n is the total number of elements in the matrix. This is because each element is visited exactly once. The space complexity is O(n) as well, as the result list stores n elements.