Rotate an image 90 degree clockwise

Problem: an image stored as a M*N matrix (two dimensional array), give an in-place algorithm to rotate it 90 degree clockwise.

Solution: First assume a simpler case where M=N, we can only use O(1) memory. Basically, each iteration we change the location of four elements (sometime, these four elements may just points to the same one): a[x,y] -> a[y,N-1-x] -> a[N-1-x, N-1-y] -> a[N-1-y, x] -> a[x,y]. The algorithm is as follow:

for(int x =0; x<n; x++)
{
   y = x;
   if(y>=n-x-1) break;
   for(; y<n-x-1; y++)
   {
      temp = a[x,y];
      a[x,y] = a[y,n-1-x];
      a[y,n-1-x] = a[n-1-x,n-1-y];
      a[n-1-x,n-1-y] = a[n-1-y,x];
      a[n-1-y,x] = temp;
   }
}

If N!=M, things will be complex, we may need an auxiliary array to track if we had visited some elements or not, the algorithm (may not be optimal) is as follow:

int visited[N][M];
  int i,j;
  for(i=0; i<N; i++)
  for(j=0; j<M; j++)
        visited[i][j] = 0;

  for(i=0; i<N; i++)
  for(j=0; j<M; j++)
  {
        if(visited[i][j]==0)
        {
           int tmp = a[i][j];
           int c_i = i;
           int c_j = j;

           do
           {
             int ii = c_j;
             int jj = N - 1 - c_i;

             int to_i = (ii*N + jj + 1)/M;
             int to_j = (ii*N + jj + 1)%M;

             if(to_j==0)
             {
                to_i--;
                to_j = M - 1;
             }
             else to_j--;

             int tmp1 = a[to_i][to_j];
             a[to_i][to_j] = tmp;
             visited[to_i][to_j] = 1;
             c_i = to_i;
             c_j = to_j;
             tmp = tmp1;
           }
           while(!(c_i==i && c_j==j));
  }
}

Related:  In-place matrix transposition