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.