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]

Difficulty: interview

Starter code:

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        

Solutions:
class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         result = []
         if not matrix:
             return result
         top = left = 0
         bottom, right = len(matrix) - 1, len(matrix[0]) - 1
         while top < bottom and left < right:
             for i in range(left, right):
                 result.append(matrix[top][i])
             for i in range(top, bottom):
                 result.append(matrix[i][right])
             for i in range(right, left, -1):
                 result.append(matrix[bottom][i])
             for i in range(bottom, top, -1):
                 result.append(matrix[i][left])
             left += 1
             right -= 1
             top += 1
             bottom -= 1
         if left == right and top == bottom:
             result.append(matrix[left][top])
         if left == right and top != bottom:
             for i in range(top, bottom+1):
                 result.append(matrix[i][left])
         if left != right and top == bottom:
             for i in range(left, right+1):
                 result.append(matrix[top][i])
         return result

class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         if not matrix:
             return []
         def layer(width, height, top, left):
             if not (width > 0 and height > 0):
                 return
             for i in range(left, left+width):
                 yield matrix[top][i]
             if height != 1:
                 for i in range(top+1, top+height):
                     yield matrix[i][left+width-1]
                 for i in range(left+width-2, left-1, -1):
                     yield matrix[top+height-1][i]
                 if width != 1:
                     for i in range(top+height-2, top, -1):
                         yield matrix[i][left]
             yield from layer(width-2,height-2, top+1, left+1)
         return list(layer(len(matrix[0]), len(matrix), 0, 0))

class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         m = matrix
         ml = len(m)
         if ml == 0:
             return []
         nl = len(m[0])
         ms, me, ns, ne = 0, ml - 1, 0, nl - 1 
         ans = []
         while ns <= ne or ms <= me: 
             #print(ms,me,ns,ne)
             if ms <= me: 
                 for j in range(ns, ne + 1): 
                     ans.append(m[ms][j])
                 ms += 1
             #print(ms,me,ns,ne)
             if ne >= ns: 
                 for j in range(ms, me + 1): 
                     ans.append(m[j][ne])
                 ne -= 1
             #print(ms,me,ns,ne)
             if me >= ms: 
                 for j in range(ne, ns - 1, -1):
                     ans.append(m[me][j])
                 me -= 1
             #print(ms,me,ns,ne)
             if ns <= ne: 
                 for j in range(me, ms - 1, -1):
                     ans.append(m[j][ns])
                 ns += 1
             #print(ms,me,ns,ne)
         return ans 

class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         if not matrix:
             return matrix
         res = []
         row = len(matrix)
         col = len(matrix[0])
         left = 0
         right = col - 1
         down = row - 1
         up = 0
         direction = 0
         while True:
             if direction == 0:
                 for i in range(left, right + 1):
                     res.append(matrix[up][i])
                 up += 1
             if direction == 1:
                 for i in range(up, down + 1):
                     res.append(matrix[i][right])
                 right -= 1
             if direction == 2:
                 for i in reversed(range(left, right+1)):
                     res.append(matrix[down][i])
                 down -= 1
             if direction == 3:
                 for i in reversed(range(up, down + 1)):
                     res.append(matrix[i][left])
                 left += 1
             direction = (direction + 1) % 4
             if left > right or up > down:
                 return res

class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         res = []
         if not matrix:
             return res
         
         left, right, top, bottom = 0, len(matrix[0])-1, 0, len(matrix)-1
         
         while left <= right and top <= bottom:
             res += [matrix[top][i] for i in range(left,right+1)]
             res += [matrix[i][right] for i in range(top+1,bottom)]
             res += [matrix[bottom][i] for i in range(right, left-1,-1) if top < bottom]
             res += [matrix[i][left] for i in range(bottom-1,top,-1) if left < right]
             left+=1
             right-=1
             top+=1
             bottom-=1
         return res

class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         if len(matrix) == 0:
             return []
         level = 0
         r = []
         while len(r) < len(matrix)*len(matrix[0]):
             if level%4 == 0:
                 r += matrix[level//4][level//4: len(matrix[0]) - level//4]
             elif level%4 == 1:
                 side_index = len(matrix[0]) - (level)//4 - 1
                 for i in range(level//4 + 1,len(matrix) - level//4):
                     r.append(matrix[i][side_index])
             elif level%4 == 2:
                 r += matrix[len(matrix) -1 - level//4][level//4:len(matrix[0]) - level//4 -1][::-1]
             elif level%4 == 3:
                 side_index = level//4
                 for i in range((len(matrix) -1 - level//4 -1),level//4 ,-1):
                     r.append(matrix[i][side_index])
             level +=1
         return r


class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         ans = []
         
         if len(matrix) is 0:
             return ans
         
         import numpy as np
         npa = np.array(matrix, dtype = int)
         
         r_s = c_s = 0
         r_e = len(matrix)
         c_e = len(matrix[0])
         
         go_row = True
         forward = True
         row_index = r_s
         col_index = c_e - 1
         
         while(r_s < r_e and c_s < c_e):
             if go_row:
                 # Traverse row
                 s = npa[row_index,c_s:c_e].tolist()
                 if forward:
                     r_s += 1
                     row_index = r_e -1
                 else:
                     r_e -= 1
                     row_index = r_s
                     s.reverse()
                 ans.extend(s)
                 
                 
             else:
                 # traverse col
                 s = npa[r_s:r_e, col_index].tolist()
                 if forward:
                     c_e -= 1
                     col_index = c_s
                 else:
                     c_s += 1
                     col_index = c_e - 1
                     s.reverse()
                 ans.extend(s)
                 forward = not forward
                                 
             go_row = not go_row
         
         return ans

class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         m = matrix
         ml = len(m)
         if ml == 0:
             return []
         nl = len(m[0])
         ms, me, ns, ne = 0, ml - 1, 0, nl - 1 
         ans = []
         while ns <= ne or ms <= me: 
             #print(ms,me,ns,ne)
             if ms <= me: 
                 for j in range(ns, ne + 1): 
                     ans.append(m[ms][j])
                 ms += 1
             #print(ms,me,ns,ne)
             if ne >= ns: 
                 for j in range(ms, me + 1): 
                     ans.append(m[j][ne])
                 ne -= 1
             #print(ms,me,ns,ne)
             if me >= ms: 
                 for j in range(ne, ns - 1, -1):
                     ans.append(m[me][j])
                 me -= 1
             #print(ms,me,ns,ne)
             if ns <= ne: 
                 for j in range(me, ms - 1, -1):
                     ans.append(m[j][ns])
                 ns += 1
             #print(ms,me,ns,ne)
         return ans 

class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         # 0 is right, 1 is down, 2 is left, 3 is up
         state = 0
         next_direction = [1, 2, 3, 0]
         r = []
         
         while len(matrix) > 0:
             if state == 0:
                 r += matrix[0]
                 matrix = matrix[1:]
                 state = next_direction[state]
             elif state == 1:
                 r += [m[len(matrix[0]) - 1] for m in matrix]
                 matrix = [m[:len(matrix[0]) - 1] for m in matrix]
                 state = 2
             elif state == 2:
                 r += reversed(matrix[-1])
                 matrix = matrix[:-1]
                 state = 3
             elif state == 3:
                 r += [matrix[j][0] for j in range(len(matrix) - 1, -1, -1)]
                 matrix = [m[1:] for m in matrix]
                 state = 0
                
             # Covers the case of a list of empty lists (eg. [[],[],[]])
             if len(matrix) >= 1 and not matrix[0]:
                 matrix = []
                 
         return r
         


class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         if not matrix:
             return matrix
         ans=matrix[0]
         m=len(matrix)
         n=len(matrix[0])
         row_m, column_m=n-1, m-1
         row_dir, column_dir=-1, 1
         i0, j0=0, n-1
         while  column_m>0:
             ans.extend([matrix[i0+i*column_dir][j0] for i in range(1, column_m+1)])
             i0+=column_m*column_dir
             column_m-=1
             column_dir*=-1
                 
             if row_m==0:
                 return ans
             else:
                 ans.extend([matrix[i0][j0+row_dir*i] for i in range(1, row_m+1)])
                 j0+=row_m*row_dir
                 row_m-=1
                 row_dir*=-1  
         return ans

class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         #O(n^2) time; O(1) space
         if not matrix:
             return []
         
         ans = []
         rowSize = len(matrix); colSize = len(matrix[0])       
         rowStart=0; colStart=0; rowEnd = rowSize-1; colEnd = colSize-1        
         
         while rowStart <= rowEnd and colStart <= colEnd:
             
             for colIndex in range(colStart,colEnd+1):
                 ans.append(matrix[rowStart][colIndex])
             rowStart += 1;
             
             for rowIndex in range(rowStart,rowEnd+1):
                 ans.append(matrix[rowIndex][colEnd])
             colEnd -= 1;
             
             if rowStart > rowEnd or colStart > colEnd: break                
             
             for colIndex in range(colEnd,colStart-1,-1):
                 ans.append(matrix[rowEnd][colIndex])
             rowEnd -= 1;                           
                 
             for rowIndex in range(rowEnd,rowStart-1,-1):
                 ans.append(matrix[rowIndex][colStart])
             colStart += 1;                                     
             
         return ans


class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         if not matrix or not matrix[0]:
             return []
         
         v = [[False] * len(matrix[0]) for _ in range(len(matrix))]
         res = []
         i = 0; j = 0
         m = len(matrix)
         n = len(matrix[0])
         count = 0
         dest = m * n
         way = 0  # 0> 1v 2< 3^
         offset = [(0, 1), (1, 0), (0, -1), (-1, 0)]
         while count < dest:
             res.append(matrix[i][j])
             count += 1
             v[i][j] = True
             if not (0 <= i + offset[way][0] < m) or not (0 <= j + offset[way][1] < n) or \
                 v[i + offset[way][0]][j + offset[way][1]]:
                     way = (way + 1) % 4
             i += offset[way][0]
             j += offset[way][1]
         return res


class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         
         m = len(matrix)
         if m == 0:
             return []
         n = len(matrix[0])
     
 
         visit = set()
         result = []
 
         pos = [0, 0]
         visit.add(tuple(pos))
         result.append(matrix[pos[0]][pos[1]])
 
         while len(visit) < m*n:
 
             for i in range(pos[1]+1, n):
                 
                 if (pos[0], i) in visit:
                     break
                 pos[1] = i
                 visit.add(tuple(pos))
                 result.append(matrix[pos[0]][pos[1]])
 
 
             for i in range(pos[0]+1, m):
                 
                 if (i, pos[1]) in visit:
                     break
                 pos[0] = i
                 visit.add(tuple(pos))
                 result.append(matrix[pos[0]][pos[1]])
 
             for i in range(pos[1]-1, -1, -1):
                 
                 if (pos[0], i) in visit:
                     break
 
                 pos[1] = i
                 visit.add(tuple(pos))
                 result.append(matrix[pos[0]][pos[1]])
 
             for i in range(pos[0]-1, -1, -1):
 
                 if (i, pos[1]) in visit:
                     break
 
                 pos[0] = i
                 
                 visit.add(tuple(pos))
                 result.append(matrix[pos[0]][pos[1]])
                 
         return result
                 
         return result
             


class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         output_arr = []
     
         while matrix:
     
             output_arr.extend(matrix.pop(0))
         
             tmp_arr = []
             for i in zip(*matrix):
                 tmp_arr.append(list(i))
         
             matrix = tmp_arr[::-1]
 
         return output_arr


class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         if not matrix:
             return []
         left = top = 0
         right = len(matrix[0]) - 1
         bottom = len(matrix) - 1
 
         result = []
         while left < right and top < bottom:
             for i in range(left, right):
                 result.append(matrix[top][i])
             for i in range(top, bottom):
                 result.append(matrix[i][right])
             for i in range(right, left, -1):
                 result.append(matrix[bottom][i])
             for i in range(bottom, top, -1):
                 result.append(matrix[i][left])
             left += 1
             right -= 1
             top += 1
             bottom -= 1
         if left == right and top == bottom:
             result.append(matrix[top][left])
         elif left == right:
             for i in range(top, bottom + 1):
                 result.append(matrix[i][left])
         elif top == bottom:
             for i in range(left, right + 1):
                 result.append(matrix[top][i])
         return result

class Solution:
     def spiralOrder(self, matrix):
         """
         :type matrix: List[List[int]]
         :rtype: List[int]
         """
         if len(matrix) == 0:
             return []
         if len(matrix) == 1:
             return matrix[0]
         if len(matrix[0]) == 1:
             result = []
             for m in matrix:
                 result.append(m[0])
             return result
         
         
         boxTop = -1
         boxRight = len(matrix[0])
         boxLeft = -1
         boxBottom = len(matrix)
         
         
         count = 0
         direction = [0, 1]
         ptr = [0, 0]
         predict = [0, 0]
         result = []
         
         while count < len(matrix) * len(matrix[0]):
             count += 1
             result.append(matrix[ptr[0]][ptr[1]])
             ptr[0] += direction[0]
             ptr[1] += direction[1]
             
             predict[0] = ptr[0] + direction[0]
             predict[1] = ptr[1] + direction[1]
             
             
             if direction == [0, 1] and predict[1] >= boxRight:
                 direction = [1, 0]
                 boxTop += 1
             elif direction == [1,0] and predict[0] >= boxBottom:
                 direction = [0, -1]
                 boxRight -= 1
             elif direction == [0, -1] and predict[1] <= boxLeft:
                 direction = [-1, 0]
                 boxBottom -= 1
             elif direction == [-1, 0] and predict[0] <= boxTop:
                 direction = [0, 1]
                 boxLeft += 1
             
         return result