Problem statement

https://leetcode.com/problems/spiral-matrix/

Solution

Let us use coordinate (x, y) and direction of movement (dx, dy). Each time when we reach point outside matrix we rotate. How we can rotate? We can either create array of rotations in advance or we can use the trick dx, dy = -dy, dx. Also how we understand it is time to rotate? We will write already visited elements with *, so when we see * or we go outside the grid, it is time to rotate.

Complexity

It is O(mn) both for time and space.

Code

class Solution:
    def spiralOrder(self, matrix):
        n, m = len(matrix[0]), len(matrix)
        x, y, dx, dy = 0, 0, 1, 0
        ans = []
        for _ in range(m*n):
            if not 0 <= x+dx < n or not 0 <= y+dy < m or matrix[y+dy][x+dx] == "*":
                dx, dy = -dy, dx
                
            ans.append(matrix[y][x])
            matrix[y][x] = "*"
            x, y = x + dx, y + dy
        
        return ans