LeetCode #54 Spiral Matrix

Medium

Problem

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,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]

Solution

Instead of manipulating current position, we’d like to maintain four edges and terminate process once there is no space for moving.

Moving direction should be in order of right, down, left, up.

Complexity

It’s obviously that all elements in this matrix are met only once. So time complexity is O(mn).

Because there is a list of length mn for saving result, space complexity is O(mn) as well.