Today I discuss a coding exercise:

Let us traverse a m x n matrix spirally to find the kth element. A typical method for this would look like:

int GetKth(int[,] A, int m, int n, int k)

{

if (n <1 || m < 1) return -1;

if (k <= m)

    return A[0, k-1];

if (k <= m+n-1)

   return A[k-m, m-1];

if (k <= m+n-1+m-1)

   return A[n-1, (m-1-(k-(m+n-1)))];

if (k <= m+n-1+m-1+n-2)

   return A[n-1-(k-(m+n-1+m-1)), 0];

return GetKth(A.SubArray(1,1,m-2,n-2), m-2, n-2, k-(2*n+2*m-4)));

}

Notice that this makes incremental albeit slow progress towards the goal in a consistent small but meaningful peels towards the finish.

Instead, we could also skip ahead. This will unpeel the spirals by skipping several adjacent rows and columns at a time. The value of k has to be in the upper half of the number of elements in the matrix before it is used.

6When k Is in this range, it can be reduced by 8x, 4x, 2x adjacent perimeter elements before it fits in the half of the given matrix and the above method to walk the spiral can be used. \If we skip adjacent perimeter from the outermost in the m×n matrix, we can skip over the number of elements as 2m+2n-4, 2m+2n-10, 2m+2n-20. In such cases we can quickly reduce k till we can walk the perimeter spiral of the inner matrix starting from the top left.

This follows a  pattern 2m +2 (n-2) , 2 (m-2) + 2 (n-4) , 2 (m-4) +2 (n-6), …

while ( k – ( 4m + 4n – 14) > m*n/2) {

k -= 4m + 4n – 14;

m = m – 4;

n = m – 2;

}

This pattern can be rewritten as 2(m +(n-2) ,  (m-2) +  (n-4) ,  (m-4) + (n-6), …)

which can be written as 2 (m+n-2(0+1), m+n-2 (1+2), m+n-2 (2+3), …)

which can be written as Sum (I = 0, 1, 2 …)(4m + 4n – 4 (I + I +1))

which can be written as Sum (I = 0, 1, 2 …)(4m + 4n – 8i – 4)