using Javascript

Direction

Rotate a 2D array (n x n matrix) 90 degree close-wise withoutcreating a new array.

For example:

Input:

const A =

[[ 1, 2, 3, 4],

[ 5, 6, 7, 8],

[ 9, 10, 11, 12],

[13, 14, 15, 16]]

rotate(A); // a function

Output:

console.log(A);

[ [ 13, 9, 5, 1 ],

[ 14, 10, 6, 2 ],

[ 15, 11, 7, 3 ],

[ 16, 12, 8, 4 ] ]

First let's examine the example and we can see that there is a pattern here

- The first row turns into the last column
- The second row turns into the second-last column
- And such that

And there are two square cycles which are

//first cycle6 7

1 2 3 4

5810 11

912

13 14 15 16

//second cycle1 2 3 45

6 78

910 1112

13 14 15 16

Since this is a 2D array, so obviously we will need one iteration inside another. The question here is “What are the range for each loop?” and “What are we going to implement in each loop cycle?”. Basically we have

for (let i = 0; i < x; i++) {

for (let j = 0; j < y; j++) {

// doing something

}

}

If we take a closer look, we will notice that for each pair of (i, j), we can spot the other three positions that in the swapping cycle. For example:

(i, j) = (0, 0)2 3

145

6 789

10 111214 15

1316

A[0][0] = 1;

A[0][3] = 4;

A[3][3] = 16;

A[3][0] = 13;

(i, j) = (0, 1)123 4

5 6 78

910 11 12

13 141516

A[0][1] =A[i][j]= 2;

A[1][3] =A[j][n - 1 - i]= 8;

A[3][2] =A[n - 1 - i][n - 1 - j]= 15;

A[2][0] =A[n - 1 - j][i]= 9;

we can perform the swaps using a temporary variable

k = A[i][j];

A[i][j] = A[n - 1 -j][i];

A[n - 1 -j][i] = A[n - 1 - i][n - 1 -j];

A[n - 1 - i][n - 1 - j] = A[j][n - 1 - i];

A[j][n - 1 -i] = k

// after swapping

(i, j) = (0, 0)2 3

1315

6 789

10 111214 15

164

(i, j) = (0, 1)1393 1

5 6 721510 11 12

16 1484

Therefore, we can swap 4 numbers in a single round of loops. We could also come to a deduction that **x **will definitely smaller than n but how small exactly is it to **n**?. Plausible thought is that x = n / 2 but what if n is an odd number? Well we can round it up, yet a question arise, should we round it up or round it down? Let’s figure it out by trying on a 3 x 3 matrix

1 2 3

4 5 6

7 8 9

n = 3;

x = n / 2 = 1.5;// should x be 1 or 1.5 ?

(i, j) = (0, 0)123

4 5 6789

(i, j) = (0, 1)

123456

789

In this example, we know that **i** would not make it to the second row, so we might conclude that x = Math.floor(n / 2) . Now we have figured out **x** in the first iteration. Let’s move on with **y** in the second loop. Should **j **run from **0 to n – 1**? Let’s try out some more examples for our first matrix.

(i, j) = (0, 2)13 951146 7 2

15 10 113

16128 4

(i, j) = (0, 3) // this position is already swapped

Our current matrix13 9 5 1146 721510 11316 12 84

Now, we know that y < n – 1 . By the moment we finish the loop for the first row, the first cycle has already been swapped, so it would not make any sense if we continue to have **j** run from 0 and it would also not a good idea if we run **j** to the last column(n – 1) as well because it is going to mess up our first cycle. Therefore, **j** obviously has some correlation with **i. **Let’s continue our swapping with the second row in the example.

(i, j) = (1, 0) // this would mess up our first cycle => definite not let j run from j.

(i, j) = (1, 1)13 9 5 1

146 72

1510 113

16 12 8 4

will turn into

13 9 5 1

1410 62

1511 73

16 12 8 4

We can see that **j** is likely to run from **i to n-1-i. **Since we have figured out the range and the implementation, we have wrap up our programming

function rotate(matrix) {

const n = matrix.length;

const x = Math.floor(n/ 2);

const y = n - 1;

for (let i = 0; i < x; i++) {

for (let j = i; j < y - i; j++) {

k = matrix[i][j];

matrix[i][j] = matrix[y - j][i];

matrix[y - j][i] = matrix[y - i][y - j];

matrix[y - i][y - j] = matrix[j][y - i]

matrix[j][y - i] = k

}

}

}

Since we are expected to not create another array, we are going to modify the input array directly. If you want to test out the function, you can see it here

Note: Since this challenge restricts us from creating another new array, the solution could only work for a **square** matrix.

#### References

Inplace rotate square matrix by 90 degrees | Set 1 – GeeksforGeeks