48. Rotate Image

Array

Description

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example cases

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints

n == matrix.length == matrix[i].length
1 $<=$ n $<=$ 20
-1000 $<=$ matrix[i][j] $<=$ 1000

Approach

주어진 행렬을 시계방향으로 90도 회전한 행렬을 반환하는 문제이다. 문제 조건이 in-place 이므로 주어진 행렬을 직접 수정해야한다.
가장 바깥쪽 테두리 영역부터 회전을 시작해서 안쪽까지 회전시키면 되는데, 먼저 행렬의 왼쪽과 오른쪽 인덱스를 가리키는 l, r 변수와, 행렬의 위족과 아래쪽 인덱스를 가리키는 t, b 변수 총 4개의 인덱스를 움직이며 회전시킨다.
matrix[t][l]은 좌측상단을 시작으로 오른쪽으로 한칸씩 움직이고, matrix[t][r]은 우측상단부터 시작해서 밑으로 한칸씩, matrix[b][r]은 우측하단부터 시작해서 왼쪽으로 한칸씩, matrix[b][l]은 좌측하단부터 시작해서 위로 한칸 씩 움직인다.
그림으로 그려보면서 풀면 이해가 빠르다. 4개의 점이 회전을 끝내면 테두리의 모든 점이 회전할 때까지 루프를 돌리고, 한 테두리의 모든 점이 회전을 끝내면 안쪽 테두리로 이동시킨다. 이때 l += 1 r -= 1 t += 1 b -= 1로 한칸씩 좁히고 이 점을 시작으로 다시 루프를 돌려 회전 시키면 된다.

Solution Code

var rotate = function(matrix) {
  const n = matrix.length
  let l = 0;
  let r = n - 1;
  let t = 0;
  let b = n - 1;
 
  while (l < r) {
      for (let i = 0; i < r - l; i += 1) {
          let tmp = matrix[t][l + i]
          matrix[t][l + i] = matrix[b - i][l]
          matrix[b - i][l] = matrix[b][r - i]
          matrix[b][r - i] = matrix[t + i][r]
          matrix[t + i][r] = tmp
      }
      l += 1;
      r -= 1;
      t += 1;
      b -= 1;
  }
};

Complexity

time complexity : $O(n^2)$
space complexity : $O(1)$

36. Valid Sudoku 53. Maximum Subarray