Katkat
Back

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

GarminSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.