หมุน Square Matrix 90 องศาใน JavaScript (In-Place)

ปัญหา: หมุนเมทริกซ์ n×n 90 องศา Clockwise แบบ In-Place

เงื่อนไข: ห้ามจัดสรรอาร์เรย์ใหม่ ต้องหมุนภายในอาร์เรย์เดิม

ตัวอย่าง

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

วิธีการ: Transpose + Reverse Rows

1. Transpose: สลับแถวกับคอลัมน์ (swap arr[i][j] ↔ arr[j][i])
2. Reverse each row: กลับลำดับในแต่ละแถว

โค้ดตัวอย่าง

const arr = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

const rotateArray = (arr = []) => {
  const n = arr.length;
  
  // Step 1: Transpose (swap across diagonal)
  for (let rowIndex = 0; rowIndex < n; rowIndex++) {
    for (let colIndex = rowIndex + 1; colIndex < n; colIndex++) {
      [arr[colIndex][rowIndex], arr[rowIndex][colIndex]] = 
      [arr[rowIndex][colIndex], arr[colIndex][rowIndex]];
    }
  }
  
  // Step 2: Reverse each row
  for (let rowIndex = 0; rowIndex < n; rowIndex++) {
    for (let colIndex = 0; colIndex < n / 2; colIndex++) {
      [arr[rowIndex][n - colIndex - 1], arr[rowIndex][colIndex]] = 
      [arr[rowIndex][colIndex], arr[rowIndex][n - colIndex - 1]];
    }
  }
};

rotateArray(arr);
console.log(arr);

ผลลัพธ์

[ [ 7, 4, 1 ], [ 8, 5, 2 ], [ 9, 6, 3 ] ]

วิธีอื่น: Layer by Layer (Single Pass)

const rotateLayer = (matrix) => {
  const n = matrix.length;
  
  for (let layer = 0; layer < Math.floor(n / 2); layer++) {
    const first = layer;
    const last = n - 1 - layer;
    
    for (let i = first; i < last; i++) {
      const offset = i - first;
      
      // Save top
      const top = matrix[first][i];
      
      // Left -> Top
      matrix[first][i] = matrix[last - offset][first];
      
      // Bottom -> Left
      matrix[last - offset][first] = matrix[last][last - offset];
      
      // Right -> Bottom
      matrix[last][last - offset] = matrix[i][last];
      
      // Top -> Right
      matrix[i][last] = top;
    }
  }
};

หมุนทวนเข็มนาฬิกา (Counter-clockwise)

const rotateCounterClockwise = (arr) => {
  // Transpose + Reverse Columns (แทน Reverse Rows)
  const n = arr.length;
  
  // Transpose
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      [arr[i][j], arr[j][i]] = [arr[j][i], arr[i][j]];
    }
  }
  
  // Reverse each column
  for (let col = 0; col < n; col++) {
    for (let row = 0; row < n / 2; row++) {
      [arr[row][col], arr[n - 1 - row][col]] = [arr[n - 1 - row][col], arr[row][col]];
    }
  }
};

ความซับซ้อน

• Time: O(n²) - ต้องเข้าถึงทุก element
• Space: O(1) - In-place
• ทั้งสองวิธีให้ผลลัพธ์เดียวกัน วิธี Layer ใช้การเขียนน้อยกว่าเล็กน้อย