Rotate an N × N matrix 90 degrees clockwise

Question

Given the problem from "Cracking the coding interview"

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees clockwise.

For simplicity I assumed a matrix of strings for my example so

[["a", "a", "a", "a"],
["b", "b", "b", "b"],
["c", "c", "c", "c"],
["d", "d", "d", "d"]]

becomes

[["d", "c", "b", "a"],
["d", "c", "b", "a"],
["d", "c", "b", "a"],
["d", "c", "b", "a"]]

Here's my JavaScript solution

var rotate = function(matrix) {
    // Copy the original matrix
    var origMatrix = matrix.slice();
    for(var i=0; i < matrix.length; i++) {
        // Map each row entry to its rotated value
        var row = matrix[i].map(function(x, j) {
            var k = (matrix.length - 1) - j;
            return origMatrix[k][i];
        });
        matrix[i] = row;
    }
    return matrix;
};

Answer 1

Are you up to date?

There is really not much to the problem and there are a variety of solutions.

It is also hard to know what the interviews are looking for. For some it is knowledge of latest language features, for others it may be judged on efficiency.

These very simple tests are generally just to see if you can actually write code. You would be amazed at how many people apply for jobs they are not able to do.

Assessing the code.

Looking at your code as a conservative HR interested in your code writing style, and up to date language knowledge.

It is a pass, you can code, you have the job but will have you in supervision for a while..You also need to catch up on the language as you are not using ES6 to the full.

General points

• You need to use const for constants, and let for block scope variables.
• You have not used any arrow functions.
• I would question why you created the function using an expression, rather than a function statement, to make sure that you know the difference. (You should play it safe an use function statements)
• Also maybe a little to much code, but not really an issue.
• Code logic.. i would ask why you chose to duplicate the array rather than just create a new one as you went.

A quick rewrite

I am assuming the rotate is in place (original array) with new rows

function rotate(matrix) {          // function statement
    const N = matrix.length - 1;   // use a constant
    // use arrow functions and nested map;
    const result = matrix.map((row, i) => 
         row.map((val, j) => matrix[N - j][i])
    );
    matrix.length = 0;       // hold original array reference
    matrix.push(...result);  // Spread operator
    return matrix;
}

Some extras

The problem states "image" and "pixel" which give a hint that this may be judged on performance. They would tell you if it was. But if you get a similar challenge and performance is important then its best to use good old for loops, avoiding any iterators that use callbacks.

Also a performance oriented function would swap in place rather than create new arrays. If you had to do that realtime with images for modern displays your code would be making big GC hits (Garbage Collection).

An alternative

Another way it can be done by rotating 4 pixels at a time can reduce memory overheads and processing time. Destructing lets you swap 4 corners in one go without the need to create temp variables.

I would never recommend you submit the following unless there was a clear directive for performance, and thinking outside the box.

// Commented version 

// N*N is square
// pixels are rotated inplace
// 4 by 4 rotated in 4 iterations
// 5 by 5 rotated in 7 iterations
function rotatePixels(image) {
    var x, y, x1, y1, edge;
    // Solve by swapping 4 at a time in rings from the outside in
    const N = image.length;  // size of array 
    const N1 = N - 1;        // position of end item 
    const N2 = N / 2;        // Half way position
    
    // x,y hold the a cell coordinate
    x = y = 0; 

    // x,y hold the diagonally opposite cell
    x1 = y1 = N1;

    // length of current edge 
    edge =  N1; 

    // while not at the center
    while (y < N2) {
        // for each item on the current edge
        while (x < edge) { // rotate points at outer edge
            // swap 4 corner items 
            // using array destructed assignment
            [   
                image[x ][y1], 
                image[y1][x1], 
                image[x1][N1 - y1],
                image[y ][x ]
            ] = [
                image[y ][x ], 
                image[x ][y1], 
                image[y1][x1], 
                image[x1][N1 - y1]
            ];
            x += 1;     // move top pos forward one
            x1 -= 1;    // move bottom pos back one
        }
        y += 1;         // diagonally into array
        x  = y;         // x same as y
        y1 = x1 = N1-x; // and diagonal opposite
        edge -= 1;      // shorten the end
    }
    return image;
} 




// How I would present it

function rotatePixels(image) {
    var x, y, x1, y1, edge;
    const N = image.length;  
    const N1 = N - 1;       
    const N2 = N / 2;    
    x = y = 0; 
    edge = x1 = y1 = N1;
    while (y < N2) {
        while (x < edge) { 
            [image[x][y1], image[y1][x1], image[x1][N1-y1], image[y][x]] =
            [image[y][x] , image[x ][y1], image[y1][x1]   , image[x1][N1-y1]];
            x += 1;
            x1 -= 1;
        }
        x  = y += 1;     
        y1 = x1 = N1-x;
        edge -= 1;
    }
    return image;
} 


// At time of writing I was unsure as to the performance of the swap using destructuring
// Turns out it is very bad
// The next version is a more conventional swap and runs 3 time faster than the above version
// and 8 times faster than the conventional solution at top of answer

function rotatePixels(image) {
    var x, y, x1, y1, edge;
    const N = image.length;  
    const N1 = N - 1;       
    const N2 = N / 2;    
    x = y = 0; 
    edge = x1 = y1 = N1;
    while (y < N2) {
        while (x < edge) { 
            const a = image[y][x];
            image[y][x]      = image[x1][N1-y1];
            image[x1][N1-y1] = image[y1][x1];
            image[y1][x1]    = image[x][y1]; 
            image[x][y1]     = a;
            x += 1;
            x1 -= 1;
        }
        x  = y += 1;     
        y1 = x1 = N1-x;
        edge -= 1;
    }
    return image;
} 
 

Answer 2

Cloning the matrix

.slice is a good way to copy the values of an array, instead of getting a reference to the same array. Unfortunately all your values are themselves arrays, which you are still using a reference to and not a copy. In this code you are not changing individual values, but setting entire rows at a time, so it still works, but this could easily lead to unexpected behavior if you are not careful.

You don't mention if you have to modify the original matrix or return a new one (you are doing both). But if you leave the original unmodified, you don't even need to make a copy. Just start out with empty array and .push each new row to it.

Mapping the values

Your .map is a bit weird. You use it on one array, but then you don't even use the value and just use the index to access a different array. This can also be done simpler. The Nth row in the result is the Nth column in the input. So using .map on the input and getting the right value from each row will give you the new row (you have to reverse it too).

var row = matrix.map(function(e) {
    return e[i]
}).reverse();

ES6

A lot of new features was introduced in ES6, which was finalized back in 2015. You should be using them by now. This means using let instead of var, and arrow functions, which are excellent for short inline function like the one above.

The final code

Another small change I made was to change to the loop to loop over the inner array. This way it also works for matrices of different dimensions.

function rotate(matrix) {
    let result = [];
    for(let i = 0; i < matrix[0].length; i++) {
        let row = matrix.map(e => e[i]).reverse();
        result.push(row);
    }
    return result;
};

Answer 3

If performance is important, as mentioned above, it would be good to use for.

Also it is nice if you show an example of how you would structure a basic class. E.g:

class Matrix {

  constructor(n){
    this.m = [];
    var z = 0;
    for (let i = 0; i < n; ++i) {
      this.m[i] = [];
      for (let j = 0; j < n; ++j) {
        this.m[i][j] = z;
        z++;
      }
    }
  }

  printMatrix() {
   console.log(this.m);
  }

  rotateMatrix() {    
    const n = this.m[0].length;

    let res = []

    for (let i = 0; i < n; ++i) {
      for (let j = 0; j < n; ++j) {
         if (!res[j])
           res[j] = []
         res[j][i] = this.m[n-1-i][j];
      }
    }
    return res;
  }
}

let m = new Matrix(5);
m.printMatrix();
let t0 = performance.now();
console.log(m.rotateMatrix());
let t1 = performance.now();
console.log("Call to rotate took " + (t1 - t0) + " milliseconds.");

It seems to perform 20% faster than using the algorithms above. I am pretty sure this can be done even more efficient.