Value on the Secondary Diagonal of a Center-Out Clockwise Spiral Matrix

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

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:

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

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

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

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.

Secondary-Diagonal Value in a Center-Out Clockwise Spiral

Hints

1. 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?
2. 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.
3. 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.

Approach

Algorithm: with m = (n - 1) // 2, the target cell is (m + k, n - 1 - (m + k)) = (m + k, m - k), i.e. it is offset k rows and -k columns from the center (m, m). For k < 0 it is the top-right corner of the square layer at distance d = -k around the center; for k > 0 it is the bottom-left corner of the layer at distance d = k; for k = 0 it is the center. Return (1 - 2k)^2 when k <= 0 and 4k^2 + 1 when k > 0.

Invariant: the walk's moves never depend on n; n only decides when it stops. So every cell receives the same number in every matrix large enough to contain it (the 3 x 3 spiral is the inner block of the 5 x 5 spiral, and so on).

Correctness: for the odd size n' = 2d + 1 the rules state that the walk ends by writing n' * n' in the top-right corner, which is offset (-d, +d) from the center. By the invariant, that cell holds (2d + 1)^2 in every larger matrix too, which gives the k = -d case. Within layer d the walk reaches the bottom-left corner (offset (+d, -d)) and then takes 2d steps up the left side to the top-left corner and 2d steps right along the top to the top-right corner, all inside layer d. So the bottom-left corner is written 4d numbers earlier and holds (2d + 1)^2 - 4d = 4d^2 + 1, which gives the k = d case. Both formulas give 1 at k = 0, the center.

Edge cases: n = 1 allows only k = 0 and returns 1. k = -m returns n * n and k = m returns n * n - 2(n - 1). The largest answer is 1001 * 1001 = 1,002,001 and every intermediate value (side * side, 4k^2) is at most that, so 32-bit integers never overflow.

• Time complexity: O(1)
• Space complexity: O(1)