Spiral Matrix III

Medium
904.

Spiral Matrix III

Spiral Matrix III is a medium coding problem on arrays, matrix and simulation, asked in Amazon, Google and Flipkart interviews.

Start at (rStart, cStart) in a rows × cols grid, facing east, and walk a clockwise spiral. Whenever the walk leaves the grid you keep going in the same pattern but visit nothing, and you re-enter later.

Return the coordinates of the grid cells in the order they are visited, until all rows · cols cells have been seen.

Example 1

Input
rows = 1, cols = 4, rStart = 0, cStart = 0
Output
[[0,0],[0,1],[0,2],[0,3]]

Example 2

Input
rows = 2, cols = 2, rStart = 0, cStart = 0
Output
[[0,0],[0,1],[1,1],[1,0]]

Example 3

Input
rows = 1, cols = 1, rStart = 0, cStart = 0
Output
[[0,0]]

Constraints

  • 1 <= rows, cols <= 100
  • 0 <= rStart < rows
  • 0 <= cStart < cols
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} rows
 * @param {number} cols
 * @param {number} rStart
 * @param {number} cStart
 * @return {number[][]}
 */
var spiralMatrixIII = function(rows, cols, rStart, cStart) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Spiral Matrix III — Solution in Python, Java & C++

Spiral Matrix III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and matrix.

Spiral Matrix III is a medium coding problem on arrays, matrix and simulation, asked in Amazon, Google and Flipkart interviews.

  • Difficulty: Medium
  • Topics: Arrays, Matrix, Simulation
  • Asked at: Amazon, Google, Flipkart
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Start at (rStart, cStart) in a rows × cols grid, facing east, and walk a clockwise spiral. Whenever the walk leaves the grid you keep going in the same pattern but visit nothing, and you re-enter later.

Return the coordinates of the grid cells in the order they are visited, until all rows · cols cells have been seen.

Example 1

Input: rows = 1, cols = 4, rStart = 0, cStart = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2

Input: rows = 2, cols = 2, rStart = 0, cStart = 0
Output: [[0,0],[0,1],[1,1],[1,0]]

Example 3

Input: rows = 1, cols = 1, rStart = 0, cStart = 0
Output: [[0,0]]

Constraints

  • 1 <= rows, cols <= 100
  • 0 <= rStart < rows
  • 0 <= cStart < cols

Hints for Spiral Matrix III

  1. Hint 1

    The spiral's leg lengths go 1, 1, 2, 2, 3, 3, … — they grow every two turns.

  2. Hint 2

    Walk the full pattern regardless of the grid, and simply skip recording anything out of bounds.

  3. Hint 3

    Stop as soon as all rows · cols cells have been recorded.

How to solve Spiral Matrix III

Follow the spiral blindly, ignoring the grid's edges, and record only the steps that land inside. The leg lengths grow by one each time the direction returns to east or west, which produces the 1, 1, 2, 2, 3, 3 pattern.

Approach

  1. Record the start, then cycle the directions east, south, west, north.
  2. Increase the leg length whenever the direction is east or west.
  3. Take that many steps, recording each in-bounds cell.
  4. Stop once the output holds rows · cols entries.

Why it works

The spiral is an unconditional geometric pattern; only the recording depends on the grid. Letting the walk wander outside keeps the pattern simple and is guaranteed to terminate, because the spiral eventually encloses the whole grid — after at most about 2·(rows + cols) legs every cell has been passed.

Complexity

  • Time — O((rows + cols)²)
  • Space — O(rows · cols) for the output

Pitfalls

  • Growing the leg length every turn instead of every two turns gives the wrong path.
  • Trying to clamp the walk to the grid breaks the spiral's shape.
  • The loop must be bounded by the count of recorded cells, not by the number of steps taken.

Reference solution

Python

from typing import List

def spiralMatrixIII(rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    out = [[rStart, cStart]]
    r, c, length, d = rStart, cStart, 0, 0
    while len(out) < rows * cols:
        if d == 0 or d == 2:
            length += 1
        for _ in range(length):
            r += dr[d]
            c += dc[d]
            if 0 <= r < rows and 0 <= c < cols:
                out.append([r, c])
        d = (d + 1) % 4
    return out

Java

public static int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
    int[] dr = { 0, 1, 0, -1 };
    int[] dc = { 1, 0, -1, 0 };
    int total = rows * cols;
    int[][] out = new int[total][2];
    int cnt = 0;
    out[cnt][0] = rStart;
    out[cnt][1] = cStart;
    cnt++;
    int r = rStart, c = cStart, len = 0, d = 0;
    while (cnt < total) {
        if (d == 0 || d == 2) len++;
        for (int i = 0; i < len && cnt < total; i++) {
            r += dr[d];
            c += dc[d];
            if (r >= 0 && r < rows && c >= 0 && c < cols) {
                out[cnt][0] = r;
                out[cnt][1] = c;
                cnt++;
            }
        }
        d = (d + 1) % 4;
    }
    return out;
}

C++

vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
    int dr[4] = { 0, 1, 0, -1 };
    int dc[4] = { 1, 0, -1, 0 };
    vector<vector<int>> out;
    out.push_back({ rStart, cStart });
    int r = rStart, c = cStart, len = 0, d = 0;
    int total = rows * cols;
    while ((int) out.size() < total) {
        if (d == 0 || d == 2) len++;
        for (int i = 0; i < len; i++) {
            r += dr[d];
            c += dc[d];
            if (r >= 0 && r < rows && c >= 0 && c < cols) out.push_back({ r, c });
        }
        d = (d + 1) % 4;
    }
    return out;
}

JavaScript

var spiralMatrixIII = function(rows, cols, rStart, cStart) {
    var dr = [0, 1, 0, -1], dc = [1, 0, -1, 0];
    var out = [[rStart, cStart]];
    var r = rStart, c = cStart, len = 0, d = 0;
    while (out.length < rows * cols) {
        if (d === 0 || d === 2) len++;
        for (var i = 0; i < len; i++) {
            r += dr[d];
            c += dc[d];
            if (r >= 0 && r < rows && c >= 0 && c < cols) out.push([r, c]);
        }
        d = (d + 1) % 4;
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal