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
19
class Solution {
 public:
  vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart,
                                      int cStart) {
    const vector<int> dx{1, 0, -1, 0};
    const vector<int> dy{0, 1, 0, -1};
    vector<vector<int>> ans{{rStart, cStart}};

    for (int i = 0; ans.size() < rows * cols; ++i)
      for (int step = 0; step < i / 2 + 1; ++step) {
        rStart += dy[i % 4];
        cStart += dx[i % 4];
        if (0 <= rStart && rStart < rows && 0 <= cStart && cStart < cols)
          ans.push_back({rStart, cStart});
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
    final int[] dx = {1, 0, -1, 0};
    final int[] dy = {0, 1, 0, -1};
    List<int[]> ans = new ArrayList<>(Arrays.asList(new int[] {rStart, cStart}));

    for (int i = 0; ans.size() < rows * cols; ++i)
      for (int step = 0; step < i / 2 + 1; ++step) {
        rStart += dy[i % 4];
        cStart += dx[i % 4];
        if (0 <= rStart && rStart < rows && 0 <= cStart && cStart < cols)
          ans.add(new int[] {rStart, cStart});
      }

    return ans.stream().toArray(int[][] ::new);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> list[list[int]]:
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    ans = [[rStart, cStart]]
    i = 0

    while len(ans) < rows * cols:
      for _ in range(i // 2 + 1):
        rStart += dy[i % 4]
        cStart += dx[i % 4]
        if 0 <= rStart < rows and 0 <= cStart < cols:
          ans.append([rStart, cStart])
      i += 1

    return ans