spiral matrix

Note: Code snippet loading may take few seconds.
Generate a square matrix of size n, such that

1. it has elements from 1 to n*2 (or 0 to n*2-1)
2. lowest element is at [n,n] (or [n-1,n-1])
3. elements are arranged in a spiral order as shown in Figure.

For instance, when n=2 and n=3
M2 =           M3=
| 3 4 |           | 5   6   7 |
| 2 1 |           | 4   9   8 |
                     | 3   2   1 |

This is really simple when we consider pattern of filling these elements at an abstract level. Our general approach is to find position for element in order {1, 2, 3, ..., n*n}

We start with rightmost bottom position and put first element there. Then we decide direction to proceed in, which is horizontal in this case. For every next element, we seek a position for it in following way-
We consider adjacent positions of current position in the direction we are in, i.e. here we consider [n,n-1] and [n,n+1] (with [n,n] as our rightmost bottom position. We see if any of this is free. We generalize any position outside matrix dimensions to be non-free and thus next position we have is [n,n-1]. We fill next element in this position and keep going.
At some point, we will find no position free for next element in the direction we are in, which is signal for us to change direction. We switch to vertical direction now and keep going with same logic. This w
ay, we keep moving ahead, find a free slot and change direction if we don't find one.
Note that when we fill in last element, we no longer find free position in either direction and we are done.

Following is the C code.

// generates a spiral square matrix of n*n
// @author Girija

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    int i, j, num;
    int pi, pj;
    bool pfound;

    // setup
    int n = atoi(argv[1]);
    bool horizontal = true;
    int max_num = num*num; // starts at 1

    // allocate
    int **matrix = (int **) malloc(sizeof(int) * n * n);

    // initialize
    for(i=0; i<n; i++) {
     matrix[i] = (int *) malloc(sizeof(int) * n);
      for(j=0; j<n; j++) {
        matrix[i][j] = -1;
      }
    }

    pi = pj = n-1;

    // generate spiral matrix
    num = 1;
    while(1) {
      // place current number at pi,pj
      matrix[pi][pj] = num;
      // get position to place next number
      pfound = false;
      if(horizontal) {
        // we are following horizontal direction, check left-right empty slots first
        // check if empty slot, reset pj
        if(pj-1 >=0 && matrix[pi][pj-1] == -1) {
            pj--;
            pfound = true;
        }
        else if(pj+1 <= n-1 && matrix[pi][pj+1] == -1) {
            pj++;
            pfound = true;
        }
        if(!pfound) {
            // time to change direction
            horizontal = false;
            // reset pi
            if(pi-1 >= 0 && matrix[pi-1][pj] == -1) {
              pi--;
              pfound = true;
            }
            else if(pi+1 <= n-1 && matrix[pi+1][pj] == -1) {
              pi++;
              pfound = true;
            }
        }
      } else {
        // we are following vertical direction, check up-down empty slots first
        // check if empty slot, reset pi
        if(pi-1 >=0 && matrix[pi-1][pj] == -1) {
            pi--;
            pfound = true;
        }
        else if(pi+1 <= n-1 && matrix[pi+1][pj] == -1) {
            pi++;
            pfound = true;
        }
        if(!pfound) {
            // time to change direction
            horizontal = true;
            // reset pj
            if(pj-1 >= 0 && matrix[pi][pj-1] == -1) {
              pj--;
              pfound = true;
            }
            else if(pj+1 <= n-1 && matrix[pi][pj+1] == -1) {
              pj++;
              pfound = true;
            }
        }
      }
      // not found? we are done!
      if(!pfound)
        break;
      num++;
    }

    for(i=0; i<n; i++) {
      printf("n");
      for(j=0; j<n; j++) {
        printf("%dt", matrix[i][j]);
      }
    }
    printf("n");
}

Thanks to Template changes to add code snippet in blog and Parsing code to add to html (blog)

top k from n (k << n)

Bhai was asked this problem in one of the interviews he faced.

Given n objects and associated scores, find top k objects s.t. k is much smaller compared to n.

The most trivial approach is of course to sort n objects based on their scores and pick top k. The best known comparison based sort will do this in O(n log n) with additional pass to pick top k. And of course, this is not what is expected! We need complexity to be lower than O(n log n).

Let's focus on last part of the problem statement. What additional benefit does it give us to know that k << n? One obvious thing that comes to mind is, we are interested in correct ordering of just top k objects, remaining n-k could be unordered at the benefit of having lower complexity. Thinking in the same direction, one can try to pick k such objects such that remaining n-k are virtually ignored! But, there has to be some mechanism to pick top k. The same thing considered in opposite way will give us better insights - i.e. we get lower complexity at the expense of neglecting ordering of non-top n-k objects; meaning we don't care about them, specifically their position in ordered list.

So, is there any way where we can selectively pick elements s.t. the highest score is picked first then the second highest scored and so on? well.. this suggests none other than a max-heap! a max-heap allows you to get maximum element one at a time with delete operation. Let's see the algorithm.

1. Build heap of n objects given.
2. for i=1 to k do
1. get max element (delete from heap)

Let's see the complexity if we are doing any better than O(n log n). Step 1 above takes O(n). Refer Complexity of building heap for analysis. Step 2.1 takes O(log n) and thus step 2 takes O(k log n). In first read, one might think the complexity is O(n) + O(k log n). Let's analyze more with examples.

• n = 1024, k = 10
• n+k log n ~ 1024 + 10 * 10 ~ 1024 -> O(n)

• n = 1024, k = 200
• n+k log n ~ 1024 + 200 * 10 ~ 2000 -> O(k log n) which will approach O(n log n) as k -> n

Of course, if k -> n, this algorithm will degenerate to O(n log n)  but in given setting where k << n, case 1 above will result in linear time algorithm.
:)