Rotate a N by N matrix by 90 degrees clockwise

Question

The task:

Given an N by N matrix, rotate it by 90 degrees clockwise.

For example, given the following matrix:

[[1, 2, 3], [4, 5, 6], [7, 8, 9]] you should return:

[[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Follow-up: What if you couldn't use any extra space?

const mtx = [[1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]];

My imperative solution:

function transpose(matrix){
  const size = matrix[0].length;
  const newMatrix = JSON.parse(JSON.stringify(matrix));
  for (let rowIndex = 0; rowIndex < size; rowIndex++) {
    const row = matrix[rowIndex];
    for (let colIndex = 0; colIndex < size; colIndex++) {
      const newRowIndex = colIndex;
      const newColIndex = size - 1 - rowIndex;
      newMatrix[newRowIndex][newColIndex] = row[colIndex];
    }
  }
  return newMatrix;
};

console.log(transpose(mtx));

My declarative solution:

const transpose2 = matrix => {
  const size = matrix[0].length;
  const newMatrix = JSON.parse(JSON.stringify(matrix));
  matrix.forEach((row, rowIndex) => {
    row.forEach((val, colIndex) => {
      const newRowIndex = colIndex;
      const newColIndex = size - 1 - rowIndex;
      newMatrix[newRowIndex][newColIndex] = val;
    });
  });
  return newMatrix;
};

console.log(transpose2(mtx));

My solution to the Follow Up question:

Didn't really understand the part with "no extra space". The only solution that came to my mind was to overwrite the existing matrix with the new values and at the end clean it up by deleting the old values. ...but appending new values to old values requires extra space, doesn't it?

const transposeNoSpace = matrix => {
  const size = matrix[0].length;
  matrix.forEach((row, rowIndex) => {
    row.forEach((val, colIndex) => {
      const newRowIndex = colIndex;
      const newColIndex = size - 1 - rowIndex;
      const newVal = val[1] ? val[0] : val;
      matrix[newRowIndex][newColIndex] = [matrix[newRowIndex][newColIndex], newVal];
    });
  });
  return matrix.map(row => row.map(col => col[1]));
};

console.log(transposeNoSpace(mtx));

I'd also be interested in a pure functional solution

Answer 1

Copying 2D array

JSON is not for copying data.

const newMatrix = JSON.parse(JSON.stringify(matrix))

Should be

const newMatrix = matrix.map(row => [...row]);

Naming

The naming you use is too verbose and gets in the way of readability.

• For 2D data it is common to use row, col or x,y to refer to the coordinates of an item.

  As x and y are traditionally ordered with x (column) first and y (row) second 2D arrays don't lend them selves to that naming. It is acceptable to abbreviate to r, c or indexing 2D arrays (within the iterators, not outside)

• transpose as a function name is too general. It would be acceptable if transpose included a argument to define how to transpose the array but in this case rotateCW would be more fitting.

• For 2D data the distance from one row to the same position on the next is called the stride

• As the input array is square there is no need to get the stride from the inner array. const stride = matrix[0].length; should be const stride = matrix.length;

Rewriting your solutions

Both these solutions are \$O(n)\$ time and space.

function rotateCW(arr) {
    const stride = arr.length;
    const res = arr.map(row => [...row]);
    for (let r = 0; r < stride; r++) {
        const row = arr[r];
        for (let c = 0; c < stride; c++) {
            res[c][stride - 1 - r] = row[c];
        }
    }
    return res;
};  // << redundant semicolon. Lines end with ; or } not both

Be careful when describing a function as declarative. Though the definition is somewhat loose you should make the effort to declare all high level processing as named functions and the imperative code at the lowest level.

const rotateCW = arr => {
    const rotItem = (r, c, item) => res[r][arr.length - 1 - c] = item;
    const processRow = (row, r) => row.forEach((item, c) => rotItem(c, r, item));
    const res = arr.map(row => [...row]);
    arr.forEach(processRow);
    return res;
}

Functional

Don't get caught up on declarative, in your past questions you had the focus on functional. You should keep that focus.

In this case the core of the solution is converting a row column reference (or coordinate) into the inverse of the rotation. We rotate CW by replacing the current item by the one 90deg CCW of it. arr[y][x] = arr[stride-1-x][y]

The next example is functional and also the smallest code.

const rotateCW = arr => {
    const rotItem = (r, c) => arr[arr.length - 1 - r][c];
    const processRow = (row, r) => row.map((item, c) => rotItem(c, r));
    return arr.map(processRow);
}

or as a one liner

const rotCW = arr => arr.map((row, y) => row.map((v, x) => arr[arr.length - 1 - x][y]));

The \$O(1)\$ space solution.

The "no extra space" simply means that it should be \$O(1)\$ space complexity. This can be done via the traditional swap,

 var a = 1, b = 2;
 const temp = a;
 a = b;
 b = temp;

Or in ES6+

 var a = 1, b = 2;
 [a,b] = [b,a];

The swap does not have to be just two items but can be over as many as you want (shifting), the only requirement is that only one spare slot is needed to shift all items.

var a = 1, b = 2, c = 3, d = 4;
const temp = a;
a = b;
b = c;
c = d;
d = temp;

Or in ES6+

var a = 1, b = 2, c = 3, d = 4;
[a, b, c, d] = [b, c, d, a];

• Note The ES6 method for swapping, as a source code complexity reduction, is great...

  but the JS engine does not know you are just swapping (or shifting), it creates an array to hold all the items on the right so that it does not overwrite them when assigning the new values. That means that the ES6+ swap is \$O(n)\$ space complexity.

Example

I come from a very heavy visual related background and x,y are the most logical way to index 2D+ arrays so will use it in this example.

function rotate2DArray(arr) {
    const stride = arr.length, end = stride - 1, half = stride / 2 | 0;
    var y = 0;
    while (y < half) {
        let x = y;
        while (x < end - y) {
            const temp = arr[y][x];
            arr[y][x] = arr[end - x][y];
            arr[end - x][y] = arr[end - y][end - x];
            arr[end - y][end - x] = arr[x][end - y];
            arr[x][end - y] = temp;
            x ++;
        }
        y++;
    }
    return arr;
}

The above is very unreadable and it pays to put a little order and alignment to the source

function rotate2DArray(arr) {
    const stride = arr.length, end = stride - 1, half = stride / 2 | 0;
    var y = 0;
    while (y < half) {
        let x = y;
        const ey = end - y;
        while (x < ey) {
            const temp = arr[y][x], ex = end - x;
            arr[y ][x ] = arr[ex][y ];
            arr[ex][y ] = arr[ey][ex];
            arr[ey][ex] = arr[x ][ey];
            arr[x ][ey] = temp;
            x ++;
        }
        y++;
    }
    return arr;
}

Thus the array is rotated in place for \$O(1)\$ space.