JavaScript Rotate 2D matrix at 90 deg clockwise without creating another array

💡 2 Dimensional matrix array is n * n matrix that is created by using rows and columns. Mostly we represent row with i and column with j. So in case, we have to pick an element from the matrix we use 2D Index like [i][j].

const A = [
 [1,  2,  3,  4],
 [5,  6,  7,  8], 
 [9,  10, 11, 12],
 [13, 14, 15, 16]
];

A[row][col] = A[i][j];

// Get element from array using 2d index
A[0][0] = 1;
A[1][2] = 7;
A[3][2] = 15;

✋ Creation of 2D matrix (n * n) using an array

Let’s take an example of matrix 4 * 4, which means there are 4 rows and 4 columns.

To print values in Row we need a for loop that will run 4 times.
To print values in Column, another inner For loop will run for 4 times.

💻 Steps:

1. First, initialize an array with a new Array(n).
2. Create a variable and initialize with 1. For every iteration, we will increase its value with value++.
3. Outer & Inner for loop will run for matrix length that is 'n'.
4. Inside outer loop – assign array[i] with blank array [].
5. Inside Inner for loop assign value to array[i][j].
6. Without #4 if we perform #5 then we get an error. Uncaught TypeError: Cannot read property ‘0’ of undefined.

function create2DMatrix(n) {
    let outputArr = new Array(n);
    let value = 1;
    for (let i = 0; i < n; i++) {
       outputArr[i] = []; 
        for (let j = 0; j < n; j++) { 
            outputArr[i][j] = value++; 
        } 
    }
    return outputArr;
}

*****Run Program****

console.log(create2DMatrix(3));
const d5 = create2DMatrix(5);
console.log(d5);

*********output***

(3) [Array(3), Array(3), Array(3)]
0: (3) [1, 2, 3]
1: (3) [4, 5, 6]
2: (3) [7, 8, 9]
length: 3

(5) [Array(5), Array(5), Array(5), Array(5), Array(5)]
0: (5) [1, 2, 3, 4, 5]
1: (5) [6, 7, 8, 9, 10]
2: (5) [11, 12, 13, 14, 15]
3: (5) [16, 17, 18, 19, 20]
4: (5) [21, 22, 23, 24, 25]
length: 5

✋ Rotate 2D matrix at 90 deg clockwise without creating another array

outer for loop > 
  inner for loop >

Now we are clear that for 2D matrix program we have a need of two for loops always. Outer for loop & inner for loop.

Ok, so now understand the above diagram of the 4 * 4 matrix and we can see that there is a pattern between the original and rotated matrix.

• The first row turns into the last column.
• The second row turns into the second-last column
• Same as for the third row
• The last row turns into the first column
• And two rotation cycles are running here.

💡 First, compute indexes based on n, i, and j parameter & these computed values should be the same for each iteration to write a program.

First iteration > 1, 4, 16, 13

Let's take first element that is (0, 0) => i =  0, j = 0 & compute indexes values based on n, i, j;

1 = A[0][0] = A[i][j];
4 =  A[0][3] =  A[j][n - 1 - i]
16 = A[3][3] =  A[n - 1 - i][n - 1 - j]
13  =  A[3, 0] = A[n - 1 - j][i]

Second iteration > 2, 8, 15, 9
Start with element that is (0, 1) > i = 0 , j = 1;

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


Third iteration > 3, 12, 14, 5
Element start that is (0, 2) > i = 0 and j = 2

3 = A[0][2] = A[i][j]
12 = A[2][3] = A[j][n - i - i]
14 = A[3][1] = A[n - 1 - i][n - 1 - j]
5 = A[1][0] = A[n - 1- j][i]

💡 Let’s calculate the range for each loop ———-

So outer loop will run 2 times for 4 * 4 matrix and that is n / 2. I have marked the circle shape over elements in the above diagram.

**Formula**

OuterLoop  = Math.floor(n/ 2);

if n = 4 then it is 2.
if n  = 5 then it is 2.
if n = 7 then it is 3.

Inner For loop - For 4 * 4 matrix, Loop will run for 3 times and that is n – 1 if value of i is 0; For i = 1 , it will be n – 1 – i => 4 – 1 – 1 = 2
It will start from (0, 0) index element that is 1 then 2, and 3. 4 is already swapped in the first element 1.

***Formula**

innerLoop = n - 1 - i ;

Now understand the Swap Algorithm first – how rotation of array at 90 deg will operate.

**

1 = A[0][0] = A[i][j];
4 =  A[0][3] =  A[j][n - 1 - i]
16 = A[3][3] =  A[n - 1 - i][n - 1 - j]
13  =  A[3, 0] = A[n - 1 - j][i]

******

1 ==> 13
A[i][j] = A[n - 1 - j][i]

4 ==> 1
A[j][n - 1 - i] = A[i][j]

16 ==> 4
A[n - 1 - i][n - 1 - j] = A[j][n - 1 - i];

13 ==> 16
A[n - 1 - j][i] = A[n - 1 - i][n - 1 - j]

**

we can see n – 1 multiple time so we can assign this value in y:
y = n – 1;

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

💻 Program structure

const n = array.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++) {
      // swap logic here...
  }
}

Full Algorithm –

function rotate(matrix) {
  // Create a deep copy of 2d array first
  let rotateArr = matrix.map((a) => a.slice());
  const n = rotateArr.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++) {
      const k = rotateArr[i][j]; // put first value in temp variable
      rotateArr[i][j] = rotateArr[y - j][i];
      rotateArr[y - j][i] = rotateArr[y - i][y - j];
      rotateArr[y - i][y - j] = rotateArr[j][y - i];
      rotateArr[j][y - i] = k;
    }
  }
  return rotateArr;
}

*****Run Program*****

const d4 = create2DMatrix(4);
console.log(d4);
console.log(rotate(d4));

(4) [Array(4), Array(4), Array(4), Array(4)]
0: (4) [1, 2, 3, 4]
1: (4) [5, 6, 7, 8]
2: (4) [9, 10, 11, 12]
3: (4) [13, 14, 15, 16]
length: 4

(4) [Array(4), Array(4), Array(4), Array(4)]
0: (4) [13, 9, 5, 1]
1: (4) [14, 10, 6, 2]
2: (4) [15, 11, 7, 3]
3: (4) [16, 12, 8, 4]
length: 4

const d3 = create2DMatrix(3);
console.log(d3);
console.log(rotate(d3));

(3) [Array(3), Array(3), Array(3)]
0: (3) [1, 2, 3]
1: (3) [4, 5, 6]
2: (3) [7, 8, 9]
length: 3

(3) [Array(3), Array(3), Array(3)]
0: (3) [7, 4, 1]
1: (3) [8, 5, 2]
2: (3) [9, 6, 3]
length: 3

 const d5 = create2DMatrix(5);
 console.log(d5);
 console.log(rotate(d5));

(5) [Array(5), Array(5), Array(5), Array(5), Array(5)]
0: (5) [1, 2, 3, 4, 5]
1: (5) [6, 7, 8, 9, 10]
2: (5) [11, 12, 13, 14, 15]
3: (5) [16, 17, 18, 19, 20]
4: (5) [21, 22, 23, 24, 25]
length: 5

(5) [Array(5), Array(5), Array(5), Array(5), Array(5)]
0: (5) [21, 16, 11, 6, 1]
1: (5) [22, 17, 12, 7, 2]
2: (5) [23, 18, 13, 8, 3]
3: (5) [24, 19, 14, 9, 4]
4: (5) [25, 20, 15, 10, 5]
length: 5

JavaScript Hoisting Interview Questions & Answers | Console Programs

Trie Data Structure – Insert Search Delete & Print Program with JavaScript

JavaScript Rotate 2D matrix

0

0