Saturday, December 21, 2019

Leetcode solution 54: Sprial Matrix


Problem Statement 

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]
 Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

It's a straight forward implementation question, we can simply just simulate the spiral order and print. You can choose to do it either iteratively (see reference to download the official Leetcode solution) or use recursion.

There is this awesome one line solution from this guy which is pretty insane.
def spiralOrder(self, matrix):
    return matrix and list(matrix.pop(0)) + self.spiralOrder(zip(*matrix)[::-1])
https://leetcode.com/problems/spiral-matrix/discuss/20571/1-liner-in-Python-%2B-Ruby

Solutions

Simulation using Recursion

Time Complexity: O(M*N) where M, N is row and col of matrix
Space Complexity: O(M*N) since we used list to store the result, where M, N is row and col of matrix


References

No comments:

Post a Comment