This is the 24th day of my participation in the First Challenge 2022

Hi, I’m the watermelon guy. Today let’s do a Medium difficulty LeetCode problem: Rotate an image.

Without further ado, let’s get right to the subject.

In simple terms, it is necessary to transform a square matrix from left to right and top to bottom by rotating it 90 degrees into a square matrix from top to bottom and right to left without using an extra matrix.

LeetCode corresponds to the title:

    1. Rotate image: leetcode-cn.com/problems/ro…
  • 01.07. Rotation matrix: leetcode-cn.com/problems/ro…

I’m going to use an extra matrix

Even though they asked me not to use another matrix, I tried to write an extra matrix solution.

Because this is the easiest thing to think of and implement if they don’t limit it.

function rotate(matrix: number[] []) :void {
  const n = matrix.length;
  / / initialization
  const tmpMatrix = new Array(n);
  for (let i = 0; i < n; i++) {
    tmpMatrix[i] = new Array(n);
  }
  
  / / rotation
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      tmpMatrix[j][n - 1 - i] = matrix[i][j]
    }
  }

  // Copy back (shallow copy)
  for (let i = 0; i < n; i++) { matrix[i] = tmpMatrix[i]; }}Copy the code

The first step is to initialize a tmpMatrix, a two-dimensional array of the same size as matrix.

Then, every row of matrix from top to bottom is traversed and corresponding to every column from right to left of RET. The corresponding relation is: tmpMatrix[j][n-1-i] = matrix[I][j].

Finally, copy the tmpMatrix back to matrix.

It’s that simple.

Time O(n^2), space O(n^2)

Rotate layers from the outside to the inside

Another way is to go from the outermost layer to the innermost layer, and rotate it layer by layer, like peeling an onion.

function rotate(matrix: number[] []) :void {
  const n = matrix.length;

  for (let i = 0, len = Math.floor(n / 2); i < len; i++) { // There are n/2 layers
    const end = n - i - 1; // End index
    for (letj = i; j < end - i; j++) { swap(matrix, i, j, j, end - i); swap(matrix, i, j, end - i, end - j); swap(matrix, i, j, end - j, i); }}};function swap(matrix: number[][], a: number, b: number, c: number, d: number) {
  let tmp = matrix[a][b];
  matrix[a][b] = matrix[c][d];
  matrix[c][d] = tmp;
  // or js specific swaps
  // [matrix[a][b], matrix[c][d]] = [matrix[c][d], matrix[a][b]];
}
Copy the code

We need to swap each of these four blocks clockwise at a time. The difficulty here is to find the correspondence between the four points. To find this pattern, you have to pay attention to the direction of I and j. For a particular circle, I is constant and j is increasing.

Suppose we use matrix[x][y] to represent a point and end to indicate the position of the ending index.

The yellow part goes from left to right, x stays the same, y increases, so it’s (I, j);

The orange part goes up from top to bottom, x increases, y stays the same, but it’s on the far right, so it’s (j, end -i);

In red, x gets smaller from right to left, y stays the same, but it’s at the bottom, so end -i, end -j;

The pink part is small from the bottom up, y stays the same and it’s equal to I, so end minus j, I;

Time complexity O(n^2), space complexity O(1).

Diagonal swap + left/right swap (reverse)

This is a much simpler implementation, which is to convert the order from left to right and then top down to top down and then left to right, and then reverse it to top down and then right to left.

function rotate(matrix: number[] []) :void {
  // Switch diagonally
  const n = matrix.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      lettmp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = tmp; }}// Switch left and right
  for (let i = 0; i < n; i++) { matrix[i].reverse(); }};Copy the code

Time complexity O(n^2), space complexity O(1).

conclusion

The first solution is achieved by trying to remove the constraint of not using extra matrices when there is no idea. If the interview is not limited by space complexity, this solution can be considered.

The second solution is from the outermost layer to the innermost layer of the idea of rotation, this idea is from the Angle of “rotation”, but the realization of the corresponding relationship between the four points is easy to write wrong, careful use.

Interview encountered this problem suggested using the third solution, which is the last solution, relatively easy to understand, it is not easy to write wrong.