CareerCup

This question is a classic entry-level question at many tech companies, which is why it's included in Gayle's book.

It was one of my favorites when interviewing candidates in the 1990s, but became so popular that I got too many candidates providing a memorized answer, unable to explain the details of what they wrote. This rendered the question almost useless for interview purposes.

It's not very tricky, but many interviewers like to ask it because it requires familiarity with C/C++ rectangular-array syntax and has enough details to enable an interviewer to observe a candidate's attention to detail. The java solutions are less interesting to the interviewer. I've observed that many mid-level and senior-level candidates have trouble tracking all the details of this question, so it's not entirely inappropriate for non-entry-level positions.

An example m x n case:

    ┌       ┐
    │ a b c │
    │ d e f │
A = │ g h i │
    │ j k l │
    │ m n o │
    └       ┘
  
       ┌           ┐
       │ m j g d a │
R(A) = │ n k h e b │
       │ i l i f c │
       └           ┘

By simple inspection we can see that R[i][j] = A[m - j - 1][i], so the code to rotate the matrix 90° is fairly trivial.

As an interviewer, I'm always ecstatic when a candidate demonstrates a solution like the following, and is able to explain every aspect of it.

template <typename E, size_t M, size_t N>
auto rotate(const E (&source)[M][N], E (&target)[N][M]) 
	-> decltype(target)
{
    for (size_t i=0; i<N; ++i)
        for (size_t j=0; j<M; ++j)
            target[i][j] = source[M-j-1][i];
    return target;
}

This implementation demonstrates a number of things besides a correct answer. It works for any size matrix, provided the size is known at compile time. It shows the interviewer a little "advanced" knowledge of C++, e.g. passing arrays by reference, meta-programming with C++ templates, and familiarity with recent additions to the language like "decltype" and "auto".

There is a follow-up question that many interviewers like; some even skip right to it. I'm not fond of it because it requires a non-obvious trick which can be difficult for even excellent, experienced programmers to see without hints. This is a little unfair considering the emotional stress the interview imposes; worse, you simply can't know if a candidate knew the trick to begin with or figured it out on their own. The objective of these kinds of questions is not to stump a candidate (or for an interviewer to show off!), but rather to see how a candidate dissects problems and codes a solution.

The follow-up question is to rotate an N x N matrix "in place", that is, where source and target are the same matrix. The implication is that the algorithm should NOT use an intermediate matrix.

A 5 x 5 matrix and it's 90° rotation.

      ┌           ┐
      │ a b c d e │
      │ f g h i j │                 
  B = │ k l m n o │
      │ p q r s t │
      │ u v w x y │
      └           ┘

         ┌           ┐
         │ u p k f a │
         │ v q l g b │
  R(B) = │ w r m h c │
         │ x s n i d │
         │ y t o j e │
         └           ┘

Our first algorithm cannot be used when source and target are the same since new values will overwrite old ones before they're read (same problem as with overlapping array copies). The non-obvious "trick" is to observe first that the entries in the corners {a, e, y and u} exchange, or rather rotate, positions. This four-at-a-time rotation of values is best placed in an auxiliary function and is trivial. In C++ it's:

template <typename E>
void rotate(E& a, E& b, E& c, E& d)
{
    auto tmp = d;
    d = c;
    c = b;
    b = a;
    a = tmp;
};

Accordingly, the rotation of the matrix can then be performed through a series of these four-at-a-time rotations, first on the outer rows and columns, then working towards the center. There are N/2 "shells", and when N is odd, the central element does not rotate. We'll need to perform N-1 four-at-a-time rotations for the outermost entries, N-3 four-at-a-time rotations for one level in, and so on until the center is reached.

Following the meta-programming methodology from our first rotate function, our in-place algorithm in C++ looks like this:

template <typename E, size_t N>
auto rotateInPlace(E (&m)[N][N]) 
    -> decltype(m)
{
    // There are N/2 "shells"
    for (size_t i=0; i<N/2; i++)
    {
        // temporary variables for clarity
        const size_t top=i, bottom=N-i-1, left=i, right=N-i-1; 
		
        // i.e. n = { N-1, N-3, N-5 ... } for each i
        const size_t n = N-i*2-1; 

        // rotate the current "shell"
        for (size_t j=0; j<n; ++j)
            rotate( m[top][left+j], m[top+j][right], 
                    m[bottom][right-j], m[bottom-j][left] );
    }

    return m;
}

Please note that (contrary to some other comments on this question) the time complexity of this algorithm is still O(N²) since every element must be visited. Doing them four-at-a-time doesn't change the big-O time complexity.

Some of my colleagues aren't happy with the above C++ solutions because they only work on fixed-size matrices stored in rectangular arrays. Instead, they insist on an implementation with dynamically sized matrices because they think it somehow adds complexity to the problem. In such situations, I prefer to see candidates provide a basic Matrix class and then provide the same algorithms as above. I do NOT like candidates to write a very complicated function with pointers and extra parameters; nor do I like to see them use C-style jagged arrays, i.e. an array of array pointers, instead of a rectangular-array (can you guess why I hate such solutions?).

Something like the following Matrix class declaration is usually sufficient for the interviewer (i.e. no implementation needed):

// Simple interface for a Matrix class
template <typename E>
class Matrix 
{
public:
    Matrix(size_t heightAndWidth); // for an N x N
    Matrix(size_t height, size_t width); // for an M x N
    size_t Height() const;
    size_t Width() const;
    E& operator() (size_t row, size_t column);
    const E& operator() (size_t row, size_t column) const;
};

The underlying rotation algorithm is exactly the same for all contiguously stored, row-major matrices.

template <typename E>
Matrix<E>& rotate(const Matrix<E>& source, Matrix<E>& target) 
{
    // implementation is basically the same as above
}

One could be tempted to suggest that the Matrix class *might* implement special matrices, e.g. sparse, triangular, or symmetric; or that the matrix class could employ a novel storage strategy, e.g. column major contiguous arrays, or jagged arrays. As a candidate, I usually withhold such comments until near the end of the interview session since implementation of these Matrix classes and concomitant algorithms is non-trivial and not appropriate for an interview-question. If you do make such comments, be prepared to discuss the implications of the matrix design on the rotation algorithm. For example, some matrix classes store the data in a special format to enable very fast transpose and row-reversal operations; these operations could be used to rotate the matrix faster than using the algorithm described above. (We're also talking about VERY LARGE matrices here)

There is a performance consideration that I sometimes mention if I'm given this question as a candidate. The elements of rectangular C-arrays are stored contiguously, in row-major order. The rotate algorithm above WRITES the target matrix entries "in-order" with respect to their placement in memory; the source matrix entries are READ out-of-order. When given the choice of in-order WRITES or in-order READS, it's generally advisable to defer to the former since it may enable better compiler optimizations. However, some processors may perform better on ordered-reads instead of writes (see why?). In this case, the ONLY CORRECT ANSWER is to write it both ways and run a performance analysis experiment.

public static int[][] rotateMatrix(int[][] matrix) {
		int[][] result=new int[matrix[0].length][matrix.length];
		for(int i=result.length-1;i>=0;i--){
			for(int j=0;j<=result[0].length-1;j++){
				result[i][result[0].length-1-j]=matrix[j][i];
			}
		}
		return result;

}
Here it is in Java. p.s. no input validation

for(i=0;i<ROW;i++)
                      for(j=0;j<COLUMN;j++)
                                           b[j][ROW-1-i]=a[i][j];

for(i=N-1; i>=0; i--)
{
for(j=0;j<=M-1;j++)
{
B[j][N-1 - i] = A[i][j]


}

}

here A is original array of size N*M
here B is another auxillary array to hold data of transpose of size M*N

When you transpose the matrix then during transpose also swap the first and last columns thus
swapping like:
1 with n-1
2 with n-2
3 with n-3 proceeding like until we reach the middle column

Given:
Matrix [M x N]

Logic:
-Have 4 variable columnMin, columnMax, rowMin, rowMax
-Initialize variables as
columnMin = 0
rowMin = 0
columnMax = N
rowMax = M

Loop
if(columnMin != columnMax)
{
Print Row from Matrix [rowMin][columnMin] to Matrix [rowMin] [columnMax]
rowMin ++ ;
}
else
{
break;
}

if(rowMin != rowMin)
{
Print Column from Matrix [rowMin][columnMax] to Matrix [rowMax][columnMax]
columnMax - - ;
}
else
{
break;
}

if(columnMin != columnMax)
{
Print Row from Matrix [rowMax][columnMax] to Matrix [rowMax][columnMin]
rowMax - - ;
}
else
{
break;
}

if(rowMin != rowMin)
{
Print Column from Matrix [rowMax][columnMin] to Matrix [rowMin][columnMin]
columnMin ++ ;
}
else
{
break;
}
END LOOP

void rotate (int array[][], int n, int m) {
    int newarray[m][n], i, j;
    for(i=0;i<n;i++) {
        for(j=0;j<m;j++) {
            newarray[m-j-i][i] = array[i][j];
        }
    }
}

void rotateRight(int matrix[][SIZE], int length) {

int layer = 0;

for (int layer = 0; layer < length / 2; ++layer) {

int first = layer;
int last = length - 1 - layer;

for (int i = first; i < last; ++i) {

int topline = matrix[first][i];
int rightcol = matrix[i][last];
int bottomline = matrix[last][length - layer - 1 - i];
int leftcol = matrix[length - layer - 1 - i][first];

matrix[first][i] = leftcol;
matrix[i][last] = topline;
matrix[last][length - layer - 1 - i] = rightcol;
matrix[length - layer - 1 - i][first] = bottomline;
}
}
}

I/P : 1 2 3 4 O/P : 9 5 1
a[n][m] 5 6 7 8 b[m][n] 10 6 2
9 10 11 12 11 7 3
12 8 4

for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
		b[j][n-i-1] = a[i][j];

While doing the transpose instead of writing from first column, start writing from last column moving backward to first column

main idea: rotate each matrix's edge from outer to inner.

time efficience is O(n^2).