Solusi Leetcode - Rotate Array

Rotate array artinya memindahkan k nilai terakhir ke depan. Misalnya, rotate [1,2,3,4,5,6,7] ke kanan sebanyak 3 menghasilkan [5,6,7,1,2,3,4]. Tantangannya adalah melakukannya secara in place, tanpa array kedua.

Saya membandingkan solusi berbasis copy, solusi cyclic, dan three step reversal. Dua yang pertama memperjelas batasannya. Yang bakal saya pakai adalah versi reversal.

Baseline dengan copy

Pendekatan pertama saya menaruh setiap nilai di array baru, lalu menyalin hasilnya kembali:

function rotateNaive(nums, k) {
  const n = nums.length;
  if (n <= 1) return nums;

  k = k % n;
  const rotated = new Array(n);

  // Just put each element where it should go
  for (let i = 0; i < n; i++) {
    rotated[(i + k) % n] = nums[i];
  }

  // Copy back to original
  for (let i = 0; i < n; i++) {
    nums[i] = rotated[i];
  }
}

Cara ini jalan, tapi array rotated makan O(n) extra space. Kedua pass-nya linear, jadi time complexity-nya O(n), tapi array tambahan itu nggak perlu kalau soalnya minta hasil yang in place.

Saya melakukan loop di input sekali untuk mengisi rotated dan sekali lagi untuk menyalinnya kembali. Operasi aritmatika dan akses array-nya O(1), jadi total waktunya tetap O(n). Biaya yang jadi masalah adalah array tambahannya: ukurannya bertambah seiring n.

Percobaan cyclic in place dan biayanya

Lalu saya mencoba memindahkan setiap nilai langsung ke tujuannya dengan mengikuti cycle rotasinya:

function rotateCyclic(nums, k) {
  const n = nums.length;
  if (n <= 1) return nums;

  k = k % n;
  let count = 0;
  let start = 0;

  while (count < n) {
    let current = start;
    let temp = nums[start];

    // Follow the rotation cycle
    while (true) {
      const next = (current + k) % n;
      const nextTemp = nums[next];
      nums[next] = temp;
      temp = nextTemp;
      current = next;
      count++;

      if (current === start) break;
    }

    start++;
  }
}

Versi cyclic memakai O(1) extra space dan tetap menyentuh setiap elemen sekali. Menurut saya control flow-nya lebih susah diikuti. Loop while (count < n) membungkus loop while (true). Setiap cycle berakhir ketika if (current === start) break dijalankan. Variabel count, start, current, temp, next, dan nextTemp semuanya berukuran konstan, tapi satu off by one error aja bisa merusak hasilnya.

Loop luar while (count < n) memastikan jumlah total perpindahannya tetap linear. Jadi logika cycle ini butuh O(n) time dan O(1) extra space, tapi kebenarannya nggak sejelas pendekatan reversal.

Tiga kali reversal

Ide in place yang lebih simpel adalah me-reverse seluruh array, me-reverse k nilai pertama, lalu me-reverse sisa nilainya. Untuk [1,2,3,4,5] yang di-rotate ke kanan sebanyak 2:

[5,4,3,2,1] setelah semuanya di-reverse, [4,5,3,2,1] setelah dua nilai pertama di-reverse, dan [4,5,1,2,3] setelah sisanya di-reverse.

Urutan langkah itu menaruh k nilai terakhir dari array asli di depan dan mengembalikan urutannya:

function rotate(nums, k) {
  const n = nums.length;
  if (n <= 1) return nums;

  k = k % n;
  if (k === 0) return nums;

  // Step 1: Flip entire array
  let start = 0;
  let end = n - 1;
  while (start < end) {
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start++;
    end--;
  }

  // Step 2: Flip first k elements
  start = 0;
  end = k - 1;
  while (start < end) {
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start++;
    end--;
  }

  // Step 3: Flip remaining n-k elements
  start = k;
  end = n - 1;
  while (start < end) {
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start++;
    end--;
  }
}

Rotasi ke kanan mengambil k nilai terakhir dan memindahkannya ke depan n-k nilai pertama. Reversal penuh menukar posisi kedua kelompok itu dan membalik urutan di dalam setiap kelompok. Me-reverse setiap kelompok secara terpisah membetulkan urutan di dalam kelompoknya.

Ketiga loop itu melakukan paling banyak n/2 + k/2 + (n-k)/2 = n swap. Dengan batas loop berupa integer, jumlah pastinya adalah floor(n/2) + floor(k/2) + floor((n-k)/2), dan tetap O(n). Algoritma ini cuma menyimpan start, end, temp, n, dan k. Jadi, algoritma ini butuh O(n) time dan O(1) extra space. Yang disentuh cuma array aslinya.

Biaya reversal dan perbandingannya

Perbandingan ketiga implementasinya seperti ini:

Ketiga pendekatan butuh O(n) time. Versi copy memakai O(n) space, sedangkan versi cyclic dan reversal memakai O(1). Saya lebih suka reversal karena state-nya cuma beberapa index dan ketiga operasinya gampang diperiksa.

Contoh dan kesimpulan

const nums = [1, 2, 3, 4, 5, 6, 7];
console.log("Before:", nums);
rotate(nums, 3);
console.log("After:", nums); // [5, 6, 7, 1, 2, 3, 4]

Contoh ini menghasilkan [5, 6, 7, 1, 2, 3, 4] secara in place.

Versi copy dan cyclic memperlihatkan batasan space-nya, tapi tiga kali reversal memenuhi batasan itu dengan control flow yang lebih simpel. Kuncinya adalah me-reverse seluruh array dulu, lalu mengembalikan urutan dari dua kelompok yang terbentuk.