#69 · Math & Geometry

Spiral Matrix

Given an m × n matrix, return all its elements in spiral order, starting at the top-left and going clockwise.

MediumLeetCode

Computing
Depends on
Answer

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Direction table

Four (row, column) steps in clockwise order: right, down, left, up. A direction index d, advanced by (d + 1) mod 4, turns the walker clockwise.

Memory layout

Two tiny arrays of four integers.

Operation	Cost
time	O(m·n): every cell is read once

Shrinking rectangle

Four numbers (top, bottom, left, right) describe the part of the matrix not yet read. After reading each side, the corresponding boundary moves inward.

Memory layout

Four integers.

Operation	Cost
space	O(1) besides the output

Why it fits

A spiral is a walk that is forced everywhere except at the turns, and the turns happen exactly when the next step is outside the unread area.
The unread area is always a rectangle, so either four boundaries or a pair of remaining counts describe it completely.
Single rows and single columns are the tricky cases: the ring has fewer than four sides, which the guards or the segment lengths handle.

Why alternatives degrade

Reading ring by ring with index formulas only:: Without guards, a ring that is one row or one column wide is read twice.
Generating coordinates with trigonometry:: There is no closed form for the coordinates of the k-th spiral cell in a rectangle; simulation is the standard answer.
Recursion on the inner matrix:: It works but copies or slices the matrix on every level.

Four approaches, from naive to production

1 · beginner

Visited matrix, turn when blocked

time O(m·n)space O(m·n)

Move in the current direction; read each cell and mark it visited. If the next cell is outside the matrix or already visited, turn clockwise. Stop after m·n cells.

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    vector<vector<bool>> seen(rows, vector<bool>(cols, false));
    int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
    vector<int> result;
    int r = 0, c = 0, d = 0;
    for (int k = 0; k < rows * cols; k++) {
        result.push_back(matrix[r][c]);
        seen[r][c] = true;
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || seen[nr][nc]) d = (d + 1) % 4;
        r += dr[d];
        c += dc[d];
    }
    return result;
}

public List<Integer> spiralOrder(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    boolean[][] seen = new boolean[rows][cols];
    int[] dr = {0, 1, 0, -1}, dc = {1, 0, -1, 0};
    List<Integer> result = new ArrayList<>();
    int r = 0, c = 0, d = 0;
    for (int k = 0; k < rows * cols; k++) {
        result.add(matrix[r][c]);
        seen[r][c] = true;
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || seen[nr][nc]) d = (d + 1) % 4;
        r += dr[d];
        c += dc[d];
    }
    return result;
}

def spiral_order(matrix):
    rows, cols = len(matrix), len(matrix[0])
    seen = [[False] * cols for _ in range(rows)]
    dr, dc = [0, 1, 0, -1], [1, 0, -1, 0]
    result = []
    r, c, d = 0, 0, 0
    for k in range(rows * cols):
        result.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + dr[d], c + dc[d]
        if nr < 0 or nr >= rows or nc < 0 or nc >= cols or seen[nr][nc]: d = (d + 1) % 4
        r += dr[d]
        c += dc[d]
    return result

function spiralOrder(matrix: number[][]): number[] {
  const rows = matrix.length, cols = matrix[0].length;
  const seen = Array.from({ length: rows }, () => new Array<boolean>(cols).fill(false));
  const dr = [0, 1, 0, -1], dc = [1, 0, -1, 0];
  const result: number[] = [];
  let r = 0, c = 0, d = 0;
  for (let k = 0; k < rows * cols; k++) {
    result.push(matrix[r][c]);
    seen[r][c] = true;
    const nr = r + dr[d], nc = c + dc[d];
    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || seen[nr][nc]) d = (d + 1) % 4;
    r += dr[d];
    c += dc[d];
  }
  return result;
}

Flaws & bottlenecks

Needs an m × n boolean matrix.
The turn check runs for every cell, including the last.
Computing the next cell before turning is easy to reverse (you must turn before moving).

Interviewer cross-questions

Why count m·n steps instead of stopping when blocked on every side?

Say: A blocked-on-all-sides test is more complex. Every cell is read exactly once, so reading m·n cells is a simple exact stopping rule.

What if the matrix is a single row?

Say: The walker goes right to the edge, would turn down but m·n steps have been used up, so the loop ends. The turn at the very end has no effect.

How do you avoid the visited matrix?

Say: Track the unread rectangle with four boundaries, or mark cells in place.

2 · intermediate

Shrinking boundaries

time O(m·n)space O(1) besides the output

Keep top, bottom, left and right. Read the top row, right column, bottom row and left column of the current rectangle, moving each boundary inward after reading its side; guard the last two sides so a degenerate ring is not read twice.

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    int top = 0, bottom = matrix.size() - 1, left = 0, right = matrix[0].size() - 1;
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++) result.push_back(matrix[top][c]);
        top++;
        for (int r = top; r <= bottom; r++) result.push_back(matrix[r][right]);
        right--;
        if (top <= bottom) {
            for (int c = right; c >= left; c--) result.push_back(matrix[bottom][c]);
            bottom--;
        }
        if (left <= right) {
            for (int r = bottom; r >= top; r--) result.push_back(matrix[r][left]);
            left++;
        }
    }
    return result;
}

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++) result.add(matrix[top][c]);
        top++;
        for (int r = top; r <= bottom; r++) result.add(matrix[r][right]);
        right--;
        if (top <= bottom) {
            for (int c = right; c >= left; c--) result.add(matrix[bottom][c]);
            bottom--;
        }
        if (left <= right) {
            for (int r = bottom; r >= top; r--) result.add(matrix[r][left]);
            left++;
        }
    }
    return result;
}

def spiral_order(matrix):
    result = []
    top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1): result.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1): result.append(matrix[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1): result.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1): result.append(matrix[r][left])
            left += 1
    return result

function spiralOrder(matrix: number[][]): number[] {
  const result: number[] = [];
  let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
  while (top <= bottom && left <= right) {
    for (let c = left; c <= right; c++) result.push(matrix[top][c]);
    top++;
    for (let r = top; r <= bottom; r++) result.push(matrix[r][right]);
    right--;
    if (top <= bottom) {
      for (let c = right; c >= left; c--) result.push(matrix[bottom][c]);
      bottom--;
    }
    if (left <= right) {
      for (let r = bottom; r >= top; r--) result.push(matrix[r][left]);
      left++;
    }
  }
  return result;
}

Flaws & bottlenecks

Four loops and two guards: many places to make an off-by-one error.
The guards (top <= bottom, left <= right) are not obvious and are easy to forget.
Reading code is harder than the simple "turn when blocked" simulation.

Interviewer cross-questions

Why are the two guards needed?

Say: After reading the top row and right column, the rectangle may have become a single row or column. Without the guards the bottom row (or left column) would be read again in the opposite direction.

Which input shows that?

Say: A single row such as [1, 2, 3]: after the top row, top passes bottom, and reading the bottom row would output 3, 2, 1 again.

Is this faster than the visited-matrix version?

Say: Both are O(m·n). This one uses O(1) extra memory and no per-cell turn tests.

3 · advanced

Mark visited cells in place

time O(m·n)space O(1) besides the output

Walk with direction steps as in the first approach, but record visited cells by overwriting them with a sentinel that cannot be a real value, so no extra matrix is needed.

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    const int DONE = -1000;
    int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
    vector<int> result;
    int r = 0, c = 0, d = 0;
    for (int k = 0; k < rows * cols; k++) {
        result.push_back(matrix[r][c]);
        matrix[r][c] = DONE;
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || matrix[nr][nc] == DONE) d = (d + 1) % 4;
        r += dr[d];
        c += dc[d];
    }
    return result;
}

public List<Integer> spiralOrder(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    final int DONE = -1000;
    int[] dr = {0, 1, 0, -1}, dc = {1, 0, -1, 0};
    List<Integer> result = new ArrayList<>();
    int r = 0, c = 0, d = 0;
    for (int k = 0; k < rows * cols; k++) {
        result.add(matrix[r][c]);
        matrix[r][c] = DONE;
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || matrix[nr][nc] == DONE) d = (d + 1) % 4;
        r += dr[d];
        c += dc[d];
    }
    return result;
}

def spiral_order(matrix):
    rows, cols = len(matrix), len(matrix[0])
    DONE = -1000
    dr, dc = [0, 1, 0, -1], [1, 0, -1, 0]
    result = []
    r, c, d = 0, 0, 0
    for k in range(rows * cols):
        result.append(matrix[r][c])
        matrix[r][c] = DONE
        nr, nc = r + dr[d], c + dc[d]
        if nr < 0 or nr >= rows or nc < 0 or nc >= cols or matrix[nr][nc] == DONE: d = (d + 1) % 4
        r += dr[d]
        c += dc[d]
    return result

function spiralOrder(matrix: number[][]): number[] {
  const rows = matrix.length, cols = matrix[0].length;
  const DONE = -1000;
  const dr = [0, 1, 0, -1], dc = [1, 0, -1, 0];
  const result: number[] = [];
  let r = 0, c = 0, d = 0;
  for (let k = 0; k < rows * cols; k++) {
    result.push(matrix[r][c]);
    matrix[r][c] = DONE;
    const nr = r + dr[d], nc = c + dc[d];
    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || matrix[nr][nc] === DONE) d = (d + 1) % 4;
    r += dr[d];
    c += dc[d];
  }
  return result;
}

Flaws & bottlenecks

Destroys the input matrix, which is unacceptable if the caller needs it afterwards.
The sentinel must lie outside the allowed value range.
Not safe if the matrix is shared or read-only.

Interviewer cross-questions

How do you choose the sentinel?

Say: Use a value outside the guaranteed range (the problem says −100 to 100). If there is no guarantee, use a separate visited structure or a copy.

Can you restore the matrix?

Say: Yes, by remembering the output and writing it back afterwards, but that needs the output order mapped back to positions, which is the walk again.

When is in-place marking acceptable?

Say: When the matrix is your own temporary data, or when memory is the bottleneck and mutation is documented.

4 · expert

Walk by segment lengths

time O(m·n)space O(1) besides the output

Alternate horizontal and vertical segments of shrinking length: cols cells, then rows − 1, then cols − 1, then rows − 2, and so on. dir flips between +1 and −1 after each pair of segments. No visited marks, no boundaries, no turn tests.

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    int rows = matrix.size(), cols = matrix[0].size();
    int r = 0, c = -1, dir = 1;
    while (rows > 0 && cols > 0) {
        for (int i = 0; i < cols; i++) {
            c += dir;
            result.push_back(matrix[r][c]);
        }
        rows--;
        for (int i = 0; i < rows; i++) {
            r += dir;
            result.push_back(matrix[r][c]);
        }
        cols--;
        dir = -dir;
    }
    return result;
}

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    int rows = matrix.length, cols = matrix[0].length;
    int r = 0, c = -1, dir = 1;
    while (rows > 0 && cols > 0) {
        for (int i = 0; i < cols; i++) {
            c += dir;
            result.add(matrix[r][c]);
        }
        rows--;
        for (int i = 0; i < rows; i++) {
            r += dir;
            result.add(matrix[r][c]);
        }
        cols--;
        dir = -dir;
    }
    return result;
}

def spiral_order(matrix):
    result = []
    rows, cols = len(matrix), len(matrix[0])
    r, c, direction = 0, -1, 1
    while rows > 0 and cols > 0:
        for i in range(cols):
            c += direction
            result.append(matrix[r][c])
        rows -= 1
        for i in range(rows):
            r += direction
            result.append(matrix[r][c])
        cols -= 1
        direction = -direction
    return result

function spiralOrder(matrix: number[][]): number[] {
  const result: number[] = [];
  let rows = matrix.length, cols = matrix[0].length;
  let r = 0, c = -1, dir = 1;
  while (rows > 0 && cols > 0) {
    for (let i = 0; i < cols; i++) {
      c += dir;
      result.push(matrix[r][c]);
    }
    rows--;
    for (let i = 0; i < rows; i++) {
      r += dir;
      result.push(matrix[r][c]);
    }
    cols--;
    dir = -dir;
  }
  return result;
}

Flaws & bottlenecks

The counting argument (why lengths shrink by one each time) is subtle to explain.
Starting at column −1 is a trick that is easy to get wrong.
It cannot be adapted easily to other traversal orders.

Interviewer cross-questions

Why do the segment lengths shrink by exactly one?

Say: After walking a full row, one row is gone, so the next vertical segment has rows − 1 cells; after that vertical segment one column is gone, so the next horizontal one has cols − 1 cells.

Why start at (0, −1)?

Say: The first step of the first segment moves to column 0, so every step can be written the same way: move, then read.

What stops the loop?

Say: When either remaining count reaches zero there is nothing left to read; the vertical loop with rows = 0 reads nothing, and the while condition ends the walk.

Synchronized code walkthrough

Showing: Visited matrix, turn when blocked — shares the player above; click any step to jump.

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    vector<vector<bool>> seen(rows, vector<bool>(cols, false));
    int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
    vector<int> result;
    int r = 0, c = 0, d = 0;
    for (int k = 0; k < rows * cols; k++) {
        result.push_back(matrix[r][c]);
        seen[r][c] = true;
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || seen[nr][nc]) d = (d + 1) % 4;
        r += dr[d];
        c += dc[d];
    }
    return result;
}

public List<Integer> spiralOrder(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    boolean[][] seen = new boolean[rows][cols];
    int[] dr = {0, 1, 0, -1}, dc = {1, 0, -1, 0};
    List<Integer> result = new ArrayList<>();
    int r = 0, c = 0, d = 0;
    for (int k = 0; k < rows * cols; k++) {
        result.add(matrix[r][c]);
        seen[r][c] = true;
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || seen[nr][nc]) d = (d + 1) % 4;
        r += dr[d];
        c += dc[d];
    }
    return result;
}

def spiral_order(matrix):
    rows, cols = len(matrix), len(matrix[0])
    seen = [[False] * cols for _ in range(rows)]
    dr, dc = [0, 1, 0, -1], [1, 0, -1, 0]
    result = []
    r, c, d = 0, 0, 0
    for k in range(rows * cols):
        result.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + dr[d], c + dc[d]
        if nr < 0 or nr >= rows or nc < 0 or nc >= cols or seen[nr][nc]: d = (d + 1) % 4
        r += dr[d]
        c += dc[d]
    return result

function spiralOrder(matrix: number[][]): number[] {
  const rows = matrix.length, cols = matrix[0].length;
  const seen = Array.from({ length: rows }, () => new Array<boolean>(cols).fill(false));
  const dr = [0, 1, 0, -1], dc = [1, 0, -1, 0];
  const result: number[] = [];
  let r = 0, c = 0, d = 0;
  for (let k = 0; k < rows * cols; k++) {
    result.push(matrix[r][c]);
    seen[r][c] = true;
    const nr = r + dr[d], nc = c + dc[d];
    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || seen[nr][nc]) d = (d + 1) % 4;
    r += dr[d];
    c += dc[d];
  }
  return result;
}

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    int top = 0, bottom = matrix.size() - 1, left = 0, right = matrix[0].size() - 1;
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++) result.push_back(matrix[top][c]);
        top++;
        for (int r = top; r <= bottom; r++) result.push_back(matrix[r][right]);
        right--;
        if (top <= bottom) {
            for (int c = right; c >= left; c--) result.push_back(matrix[bottom][c]);
            bottom--;
        }
        if (left <= right) {
            for (int r = bottom; r >= top; r--) result.push_back(matrix[r][left]);
            left++;
        }
    }
    return result;
}

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++) result.add(matrix[top][c]);
        top++;
        for (int r = top; r <= bottom; r++) result.add(matrix[r][right]);
        right--;
        if (top <= bottom) {
            for (int c = right; c >= left; c--) result.add(matrix[bottom][c]);
            bottom--;
        }
        if (left <= right) {
            for (int r = bottom; r >= top; r--) result.add(matrix[r][left]);
            left++;
        }
    }
    return result;
}

def spiral_order(matrix):
    result = []
    top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1): result.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1): result.append(matrix[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1): result.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1): result.append(matrix[r][left])
            left += 1
    return result

function spiralOrder(matrix: number[][]): number[] {
  const result: number[] = [];
  let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
  while (top <= bottom && left <= right) {
    for (let c = left; c <= right; c++) result.push(matrix[top][c]);
    top++;
    for (let r = top; r <= bottom; r++) result.push(matrix[r][right]);
    right--;
    if (top <= bottom) {
      for (let c = right; c >= left; c--) result.push(matrix[bottom][c]);
      bottom--;
    }
    if (left <= right) {
      for (let r = bottom; r >= top; r--) result.push(matrix[r][left]);
      left++;
    }
  }
  return result;
}

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    const int DONE = -1000;
    int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
    vector<int> result;
    int r = 0, c = 0, d = 0;
    for (int k = 0; k < rows * cols; k++) {
        result.push_back(matrix[r][c]);
        matrix[r][c] = DONE;
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || matrix[nr][nc] == DONE) d = (d + 1) % 4;
        r += dr[d];
        c += dc[d];
    }
    return result;
}

public List<Integer> spiralOrder(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    final int DONE = -1000;
    int[] dr = {0, 1, 0, -1}, dc = {1, 0, -1, 0};
    List<Integer> result = new ArrayList<>();
    int r = 0, c = 0, d = 0;
    for (int k = 0; k < rows * cols; k++) {
        result.add(matrix[r][c]);
        matrix[r][c] = DONE;
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || matrix[nr][nc] == DONE) d = (d + 1) % 4;
        r += dr[d];
        c += dc[d];
    }
    return result;
}

def spiral_order(matrix):
    rows, cols = len(matrix), len(matrix[0])
    DONE = -1000
    dr, dc = [0, 1, 0, -1], [1, 0, -1, 0]
    result = []
    r, c, d = 0, 0, 0
    for k in range(rows * cols):
        result.append(matrix[r][c])
        matrix[r][c] = DONE
        nr, nc = r + dr[d], c + dc[d]
        if nr < 0 or nr >= rows or nc < 0 or nc >= cols or matrix[nr][nc] == DONE: d = (d + 1) % 4
        r += dr[d]
        c += dc[d]
    return result

function spiralOrder(matrix: number[][]): number[] {
  const rows = matrix.length, cols = matrix[0].length;
  const DONE = -1000;
  const dr = [0, 1, 0, -1], dc = [1, 0, -1, 0];
  const result: number[] = [];
  let r = 0, c = 0, d = 0;
  for (let k = 0; k < rows * cols; k++) {
    result.push(matrix[r][c]);
    matrix[r][c] = DONE;
    const nr = r + dr[d], nc = c + dc[d];
    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || matrix[nr][nc] === DONE) d = (d + 1) % 4;
    r += dr[d];
    c += dc[d];
  }
  return result;
}

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    int rows = matrix.size(), cols = matrix[0].size();
    int r = 0, c = -1, dir = 1;
    while (rows > 0 && cols > 0) {
        for (int i = 0; i < cols; i++) {
            c += dir;
            result.push_back(matrix[r][c]);
        }
        rows--;
        for (int i = 0; i < rows; i++) {
            r += dir;
            result.push_back(matrix[r][c]);
        }
        cols--;
        dir = -dir;
    }
    return result;
}

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    int rows = matrix.length, cols = matrix[0].length;
    int r = 0, c = -1, dir = 1;
    while (rows > 0 && cols > 0) {
        for (int i = 0; i < cols; i++) {
            c += dir;
            result.add(matrix[r][c]);
        }
        rows--;
        for (int i = 0; i < rows; i++) {
            r += dir;
            result.add(matrix[r][c]);
        }
        cols--;
        dir = -dir;
    }
    return result;
}

def spiral_order(matrix):
    result = []
    rows, cols = len(matrix), len(matrix[0])
    r, c, direction = 0, -1, 1
    while rows > 0 and cols > 0:
        for i in range(cols):
            c += direction
            result.append(matrix[r][c])
        rows -= 1
        for i in range(rows):
            r += direction
            result.append(matrix[r][c])
        cols -= 1
        direction = -direction
    return result

function spiralOrder(matrix: number[][]): number[] {
  const result: number[] = [];
  let rows = matrix.length, cols = matrix[0].length;
  let r = 0, c = -1, dir = 1;
  while (rows > 0 && cols > 0) {
    for (let i = 0; i < cols; i++) {
      c += dir;
      result.push(matrix[r][c]);
    }
    rows--;
    for (let i = 0; i < rows; i++) {
      r += dir;
      result.push(matrix[r][c]);
    }
    cols--;
    dir = -dir;
  }
  return result;
}