Like A Girl

Pushing the conversation on gender equality.

Code Like A Girl

Rotate an 2D matrix 90 degree clockwise without create another array.

using Javascript

Photo by Ahmad Dirini on Unsplash

Direction

Rotate a 2D array (n x n matrix) 90 degree close-wise without creating 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 cycle
1 2 3 4
5
6 7 8
9
10 11 12
13 14 15 16
// second cycle
1 2 3 4
5 6 7 8
9 10 11 12
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) 
1
2 3 4
5 6 7 8
9 10 11 12
13
14 15 16
A[0][0] = 1;
A[0][3] = 4;
A[3][3] = 16;
A[3][0] = 13;
(i, j) = (0, 1)
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
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) 
13
2 3 1
5 6 7 8
9 10 11 12
16
14 15 4
(i, j) = (0, 1)
13 9 3 1
5 6 7 2
15 10 11 12
16 14 8 4

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)
1 2 3
4 5 6
7 8 9
(i, j) = (0, 1)
1 2 3
4 5 6
7 8 9

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 9 5 1
14 6 7 2
15 10 11 3
16 12 8 4
(i, j) = (0, 3) // this position is already swapped
Our current matrix
13 9 5 1
14 6 7 2
15 10 11 3
16 12 8 4

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
14 6 7 2
15 10 11 3
16 12 8 4
will turn into 
13 9 5 1
14 10 6 2
15 11 7 3
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