Best Big O. O(rows*cols) time and O(1) extra spaces
Intuition\n Describe your first thoughts on how to solve this problem. \nThe walk order is right, down, left, up. The steps of right/down is the same, and the s
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe walk order is right, down, left, up. The steps of right/down is the same, and the steps of left/up are also the same, but it is one more step than right/down. Then the next right/down is also one more steps than the previous left/up. Suppose *ln* is the steps number, so *ln* increses by 1 for every two walk\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe walk function walk(di, y, x, ln) means walking towards di direction, start from (y, x), walk for *ln* steps. *In* the walk function, for each direction, need to calculate the first point which enter the matrix, then calculate how many grids intersecting with the matrix, for example there\'re *dist* steps. Then we call fill(di, y, x, dist), which is filling towards di direction starting from point *(y, x)* for *dist* steps\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(rows*cols)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe return takes $$O(rows*cols)$$ spaces, other than that it is only constant extra spaces: $$O(1)$$\n\n# Code\n```\ndrns = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n\nclass Solution:\n    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n        n, m = rows, cols\n        nm = n*m\n        rslts = []\n\n        # Start from (y, x), and fill in the Matrix for dist steps.\n        # If dist <= 0, do nothing\n        def fill(di, y, x, dist):\n            while dist > 0:\n                rslts.append([y, x])\n                y, x = y+drns[di][0], x+drns[di][1]\n                dist -= 1\n\n        # Walk towards di direction, start from (y, x), walk for ln steps.\n        def walk(di, y, x, ln):\n            if di == 0:\n                # right direction, x0 is the point start to fill\n                x0 = max(x, 0)\n                if 0 <= y < n:\n                    fill(di, y, x0, min(x+ln, m)-x0)\n                return y, x+ln\n\n            elif di == 1:\n                # down direction, y0 is the point start to fill\n                y0 = max(y, 0)\n                if 0 <= x < m:\n                    fill(di, y0, x, min(y+ln, n)-y0)\n                return y+ln, x\n\n            elif di == 2:\n                # left direction, x0 is the point start to fill\n                x0 = min(x, m-1)\n                if 0 <= y < n:\n                    fill(di, y, x0, x0-max(x-ln, -1))\n                return y, x-ln\n\n            else:\n                # up direction, y0 is the point start to fill\n                y0 = min(y, n-1)\n                if 0 <= x < m:\n                    fill(di, y0, x, y0-max(y-ln, -1))\n                return y-ln, x\n\n        di = 0\n        ln = 1\n        y, x = rStart, cStart\n        while len(rslts) < nm:\n            y, x = walk(di, y, x, ln)\n            # Change direction\n            di = (di+1)%4\n            # ln increses by 1 for every two walk\n            if di&1 == 0:\n                ln += 1\n\n        return rslts\n\n```
['Python3']