Problem statement

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

Solution

Let us simulate process: at each moment of time we have coordinates x, y and direction dx, dy. Then we need to take number of steps in each direction 1, 1, 2, 2, 3, 3, ... and do rotation after each sequence of steps. Rotation can be written as dx, dy = dy, -dx.

Complexity

Time complexity is O((R+C)^2), space complexity is O(RC).

Code

class Solution:
    def spiralMatrixIII(self, R, C, r0, c0):
        x, y, dx, dy = r0, c0, 0, 1
        steps, ans = 2, []
        while len(ans) != R*C:
            for s in range(steps//2):
                if 0 <= x < R and 0 <= y < C: ans.append([x,y])
                x, y = x + dx, y + dy
            dx, dy = dy, -dx
            steps += 1
        
        return ans