885.md

885. Spiral Matrix III

Solution 1 (time O(mn), space O(1))

class Solution(object):
    def spiralMatrixIII(self, rows, cols, rStart, cStart):
        """
        :type rows: int
        :type cols: int
        :type rStart: int
        :type cStart: int
        :rtype: List[List[int]]
        """
        dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
        px, py = rStart, cStart
        ans, cnt = [[px, py]], 1
        if rows * cols == 1:
            return ans
        k = 1
        while True:
            for i in range(4):
                for j in range(k + i // 2):
                    px += dx[i]
                    py += dy[i]
                    if 0 <= px < rows and 0 <= py < cols:
                        ans.append([px, py])
                        cnt += 1
                        if cnt == rows * cols:
                            return ans
            k += 2
        return []