Problems/Math and Geometry/Spiral Traversal
Math and Geometry
medium

Spiral Traversal

Traverse a 2D matrix in a clockwise, layer-by-layer fashion, returning the elements in the order visited. This problem tests your ability to work with multi-dimensional arrays and think geometrically about data structures.

matrixspiral traversalarraytwo-pointersiteration

Problem Statement

Given a rectangular matrix (a list of lists) of integers, write a function that returns a list containing all the elements of the matrix, arranged in clockwise spiral order. The spiral starts at the top-left corner and winds its way inwards, layer by layer, until all elements have been visited.

Example 1
Input: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
The spiral traversal starts at 1, goes right to 3, down to 9, left to 7, up to 4, and finally to the center element 5.
Example 2
Input: [[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]
The traversal starts at 1, goes right to 4, down to 12, left to 9, up to 5, then right to 7.
Constraints
  • -The matrix will always be rectangular (all rows have the same number of columns).
  • -The matrix can be empty (zero rows or columns).
  • -Matrix elements are integers.
  • -You must return a list of integers.
  • -The dimensions of the matrix will not exceed 100x100.

Brute Force Approach

The brute force approach would involve manually tracing the spiral path within the matrix, keeping track of visited cells to avoid duplicates. Imagine physically walking the path within the grid and marking each cell after you visit it. This method requires additional space to store which cells have been visited. Time complexity would be O(mn) since we visit each cell, and space complexity O(mn) to store visited markers.

TimeO(m*n)
SpaceO(m*n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem