LeetCode Grinding
Algorithms3 menit baca

Solusi Leetcode - Rotate Array

Rotate array ke kanan dengan tiga kali reversal dan extra space yang konstan.

Di artikel ini 5 bagian

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.

Aku membandingkan penyalinan, penelusuran cycle rotasi, dan pembalikan segmen. Aku lebih suka versi reversal karena setiap dari tiga operasinya bisa diperiksa secara terpisah.

Baseline dengan copy

Versi ini menaruh setiap value di array baru, lalu menyalin hasilnya kembali:

javascript
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];
  }
}

Mengisi rotated dan menyalinnya kembali butuh dua pass linear, jadi waktunya O(n). Array tambahan itu memakai O(n) space.

Percobaan cyclic in place dan biayanya

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

javascript
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 aku 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) berhenti setelah n perpindahan, termasuk ketika rotasi punya beberapa cycle terpisah. Total biayanya O(n) waktu dan O(1) extra space.

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:

javascript
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

PendekatanTime ComplexitySpace ComplexityKompleksitas KodeMaintainability
Naive (copy array)O(n)O(n)RendahTinggi
Pendekatan cyclicO(n)O(1)Sangat TinggiRendah
Three-step reversalO(n)O(1)RendahTinggi

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

Merotasi array contoh

javascript
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.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan