Get started

Spiral Matrix III — Medium Problem & Solution

Start at (rStart, cStart) in a rows × cols grid, facing east, and walk a clockwise spiral.

  • 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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue