Today we look at a coding exercise for spiral traversal of a m x n matrix.

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)));

}

The elements in the perimeter of the spiral follow a pattern as 

 2m +2 (n-2) , 2 (m-2) + 2 (n-4) , 2 (m-4) +2 (n-6), …

The skipping does not have to be in regular intervals of fixed number of adjacent perimeter cells of the matrix. It can progress downwards from 8x, 4x, to 2x. This is similar to exponential backoff used in LAN networks.

Int getNumberOfElementsToSkip (int m, int n, int x) {

      Int sum = 0;

      For (int I =0; I  < x; i++) {

            sum += 4*m +4 *n -8 *i- 4;

      }

      return sum;

}

Now we can try in multiples of 2 

Int getNumberOfPerimeterSpiralsToSkip( int m, int n, int k) {

     // start with 8

     Int count = getNumberOfElementsToSkip(m,n,8) 

     If (count < k && count < m *n / 2) {

          return 8;

     }

    // then with 4

count = getNumberOfElementsToSkip(m,n,4) 

     If (count < k && count < m *n / 2) {

          return 4;

     }

   // then with 2

count = getNumberOfElementsToSkip(m,n,2) 

     If (count < k && count < m *n / 2) {

          return 2;

     }

  return 1;

}