Skip to content

885. Spiral Matrix III 👎

  • Time: $O(\max^2(R, C))$
  • Space: $O(R \cdot C)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
    vector<vector<int>> ans{{r0, c0}};
    vector<int> dx{1, 0, -1, 0};
    vector<int> dy{0, 1, 0, -1};

    for (int i = 0; ans.size() < R * C; ++i)
      for (int step = 0; step < i / 2 + 1; ++step) {
        r0 += dy[i % 4];
        c0 += dx[i % 4];
        if (0 <= r0 && r0 < R && 0 <= c0 && c0 < C)
          ans.push_back({r0, c0});
      }

    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
    List<int[]> ans = new ArrayList<>();
    final int[] dx = {1, 0, -1, 0};
    final int[] dy = {0, 1, 0, -1};

    ans.add(new int[] {r0, c0});

    for (int i = 0; ans.size() < R * C; ++i)
      for (int step = 0; step < i / 2 + 1; ++step) {
        r0 += dy[i % 4];
        c0 += dx[i % 4];
        if (0 <= r0 && r0 < R && 0 <= c0 && c0 < C)
          ans.add(new int[] {r0, c0});
      }

    return ans.toArray(new int[ans.size()][]);
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def spiralMatrixIII(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
    ans = [[r0, c0]]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    i = 0

    while len(ans) < R * C:
      for _ in range(i // 2 + 1):
        r0 += dy[i % 4]
        c0 += dx[i % 4]
        if 0 <= r0 < R and 0 <= c0 < C:
          ans.append([r0, c0])
      i += 1

    return ans
Back to top