Value on the Secondary Diagonal of a Center-Out Clockwise Spiral Matrix
Company: Garmin
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
An `n x n` matrix with an odd `n` is filled with the integers `1` to `n * n` in a clockwise spiral that starts in the center cell and winds outward to the edges. Given `n` and a signed row offset `k`, return the number that sits on the secondary diagonal of the matrix, in the row that is `k` rows away from the middle row.
### Function Signature
```python
def spiral_anti_diagonal_value(n: int, k: int) -> int:
```
### Rules
- Rows are numbered `0` to `n - 1` from top to bottom, and columns `0` to `n - 1` from left to right. Let `m = (n - 1) // 2`. The middle row and the middle column both have index `m`, so the center cell is `(m, m)`.
- The spiral is a walk. Write `1` in the center cell. Then move one cell at a time and write the next integer (`2`, `3`, `4`, …) in each cell you enter. The walk takes 1 step right, 1 step down, 2 steps left, 2 steps up, 3 steps right, 3 steps down, 4 steps left, 4 steps up, and so on: the direction cycles right, down, left, up, and the run length grows by one after every two runs. The walk stops as soon as `n * n` has been written, which happens in the top-right corner `(0, n - 1)`.
- The secondary diagonal is the set of cells `(i, n - 1 - i)` for `0 <= i <= n - 1`, running from the top-right corner to the bottom-left corner.
- The target row is `r = m + k`. A negative `k` counts rows upward from the middle row, a positive `k` counts rows downward, and `k = 0` is the middle row itself. Return the value in cell `(r, n - 1 - r)`.
For `n = 5` the filled matrix is:
```text
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
```
### Constraints
- `1 <= n <= 1001`, and `n` is odd.
- `-m <= k <= m`, where `m = (n - 1) // 2`, so the target row always exists.
- The answer lies between `1` and `n * n`, which is at most `1,002,001`, so it fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: n = 5, k = -1
Output: 9
```
The middle row is `m = 2`, so the target row is `2 - 1 = 1`. Its secondary-diagonal cell is `(1, 3)`, which holds `9` in the matrix above.
**Example 2**
```text
Input: n = 5, k = 2
Output: 17
```
The target row is `2 + 2 = 4`, the bottom row. Its secondary-diagonal cell is the bottom-left corner `(4, 0)`, which holds `17`.
**Example 3**
```text
Input: n = 7, k = 3
Output: 37
```
The middle row is `m = 3`, so the target row is `6`, the bottom row, and its secondary-diagonal cell is `(6, 0)`. The bottom row of the `7 x 7` spiral reads `37 36 35 34 33 32 31` from left to right, so the answer is `37`.
Overview: A matrix coding question: an odd-sized square matrix is filled with a clockwise spiral that starts at the center cell, and you must return the number on its secondary diagonal a given number of rows above or below the middle row. It tests precise index arithmetic and reasoning about how the spiral grows outward ring by ring.
Read the full Garmin Software Engineer interview experience this question came from
An `n x n` matrix, where `n` is odd, is filled with the integers `1` to `n * n` in a clockwise spiral that starts in the center cell and winds outward to the edges. Given `n` and a signed row offset `k`, return the number that sits on the secondary diagonal of the matrix, in the row that is `k` rows away from the middle row.
### Rules
- Rows are numbered `0` to `n - 1` from top to bottom, and columns `0` to `n - 1` from left to right. Let `m = (n - 1) // 2`. The middle row and the middle column both have index `m`, so the center cell is `(m, m)`.
- The spiral is a walk. Write `1` in the center cell. Then move one cell at a time and write the next integer (`2`, `3`, `4`, ...) in each cell you enter. The walk takes 1 step right, 1 step down, 2 steps left, 2 steps up, 3 steps right, 3 steps down, 4 steps left, 4 steps up, and so on: the direction cycles right, down, left, up, and the run length grows by one after every two runs. The walk stops as soon as `n * n` has been written, which happens in the top-right corner `(0, n - 1)`.
- The secondary diagonal is the set of cells `(i, n - 1 - i)` for `0 <= i <= n - 1`, running from the top-right corner to the bottom-left corner.
- The target row is `r = m + k`. A negative `k` counts rows upward from the middle row, a positive `k` counts rows downward, and `k = 0` is the middle row itself. Return the single integer stored in cell `(r, n - 1 - r)`.
For `n = 5` the filled matrix is:
```text
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
```
### Examples
**Example 1**
```text
Input: n = 5, k = -1
Output: 9
```
The middle row is `m = 2`, so the target row is `2 - 1 = 1`. Its secondary-diagonal cell is `(1, 3)`, which holds `9` in the matrix above.
**Example 2**
```text
Input: n = 7, k = 3
Output: 37
```
The middle row is `m = 3`, so the target row is `6`, the bottom row, and its secondary-diagonal cell is `(6, 0)`. The bottom row of the `7 x 7` spiral reads `37 36 35 34 33 32 31` from left to right, so the answer is `37`.
### Constraints
- `1 <= n <= 1001`, and `n` is odd.
- `-m <= k <= m`, where `m = (n - 1) // 2`, so the target row always exists.
- The answer lies between `1` and `n * n`, which is at most `1,002,001`, so it fits in a 32-bit signed integer. No value ever exceeds `2^31 - 1`, so a 32-bit `int` return type is sufficient in Java and C++.
Constraints
- 1 <= n <= 1001, and n is odd.
- -m <= k <= m, where m = (n - 1) // 2, so the target row always exists.
- The answer lies between 1 and n * n, which is at most 1,002,001, so it fits in a 32-bit signed integer.
Examples
Input: (1, 0)
Expected Output: 1
Explanation: Minimum valid matrix: the single center cell holds 1.
Input: (5, -1)
Expected Output: 9
Explanation: Source example 1: cell (1, 3) of the 5 x 5 spiral holds 9.
Hints
- Express the target cell (m + k, n - 1 - (m + k)) as a row offset and a column offset from the center (m, m). Where does it sit relative to the square rings of cells around the center?
- The walk's moves never depend on n; n only decides when it stops. Compare the inner 3 x 3 block of the 5 x 5 matrix with the full 3 x 3 matrix.
- The rules say where n * n is written when the walk stops. Use that to work out the numbers at the corners of each ring.