Obsesi LeetCode 41 Saya: Penjelajahan Mendalam ke dalam Teka-Teki Bilangan Positif yang Hilang Pertama

Masalah "First Missing Positive" di LeetCode (nomor 41) telah menjadi obsesi ngoding terbaru saya. Ini adalah teka-teki yang tampak sederhana namun telah menguasai pikiran saya, mendorong saya untuk mengeksplorasi seluk-beluknya dan menciptakan solusi TypeScript yang paling efisien. Postingan ini bukan hanya tentang menguasai wawancara ngoding (meskipun itu adalah keuntungan yang bagus). Ini tentang kegembiraan murni dalam memecahkan masalah, sensasi optimasi, dan keindahan elegan dari kode yang efisien. Dan karena saya sedikit kutu buku matematika, kita bahkan akan mempelajari dasar-dasar matematika dari solusi ini.

Masalahnya: Serigala Berbulu Domba

Masalah ini menyajikan sebuah array bilangan bulat yang tidak terurut. Tugas Anda: temukan bilangan bulat positif terkecil yang hilang. Tampaknya mudah? Pikirkan lagi. Kendala waktu $O(n)$ dan kompleksitas ruang $O(1)$ mengubah tugas yang tampaknya sederhana ini menjadi teka-teki algoritmik yang menantang.

Perjuangan Awal: Jebakan Brute Force

Upaya awal saya melibatkan pengurutan (melanggar kendala waktu $O(n)$) dan himpunan hash (melebihi batas ruang $O(1)$). Jelas, pendekatan yang lebih canggih diperlukan.

Momen Eureka: Transformasi In-Place

Pemahaman kuncinya adalah menyadari bahwa saya dapat menggunakan array input itu sendiri sebagai tabel hash. Dengan mengatur ulang elemen, saya dapat menempatkan angka $x$ pada indeks $x - 1$ (jika $1 \le x \le n$, di mana $n$ adalah panjang array). Transformasi in-place ini membuka jalan menuju solusi yang efisien.

Evolusi Kode: Sebuah Saga TypeScript

Berikut adalah kronik evolusi kode saya, dengan penjelasan rinci dan wawasan matematika:

Versi 1: Pendekatan Naif (dengan Pertukaran yang Redundan)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length

  // Tempatkan setiap angka pada posisi yang benar jika berada dalam rentang [1, n]
  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const correctIndex = nums[i] - 1
      ;[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]] // Tukar
    }
  }

  // Temukan bilangan positif pertama yang hilang
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // Jika semua angka berada pada posisi yang benar, angka yang hilang adalah n + 1
  return n + 1
}

Versi ini, meskipun fungsional, menderita pertukaran yang berlebihan. Jumlah pertukaran dalam skenario terburuk mendekati $O(n^2)$, meskipun kasus rata-rata lebih dekat ke $O(n)$.

Penjelasan:

1. Susun ulang array: Setiap angka nums[i] ditempatkan pada indeks "benar" (nums[i] - 1) jika berada dalam rentang [1, n] dan belum berada pada posisi yang benar.

2. Identifikasi positif yang hilang: Setelah penataan ulang, indeks pertama i di mana nums[i] !== i + 1 menunjukkan bahwa i + 1 adalah bilangan bulat positif yang hilang.

3. Kembalikan n + 1 jika diperlukan: Jika semua angka dari 1 hingga n berada pada posisi yang benar, angka yang hilang adalah n + 1.

Poin Kunci:

• Penataan ulang in-place: Kita memodifikasi array itu sendiri untuk menghindari penggunaan ruang ekstra.
• Efisiensi: Baik penataan ulang dan pemindaian akhir membutuhkan waktu $O(n)$, memastikan kinerja optimal.

Versi 2: Peningkatan Kinerja (Mengeliminasi Pertukaran yang Redundan)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  // Susun ulang angka ke posisi yang benar jika memungkinkan
  while (idx < n) {
    const correctIdx = nums[idx] - 1
    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      // Tukar tanpa menggunakan variabel sementara
      ;[nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]
    } else {
      idx++
    }
  }

  // Identifikasi positif pertama yang hilang
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return n + 1
}

Penjelasan:

1. Penataan Ulang yang Efisien:

   • Perulangan while menukar elemen langsung ke posisi yang benar (nums[idx] - 1) hanya ketika angka tersebut berada dalam rentang yang valid [1, n] dan belum berada pada posisi yang benar.
   • Kondisi if memastikan angka yang tidak valid atau sudah benar dilewati tanpa pertukaran yang tidak perlu.

2. Pemeriksaan Indeks Langsung:

   • Selama fase penataan ulang, pertukaran yang tidak valid dan operasi yang berlebihan dihindari dengan memeriksa rentang dan nilai nums[idx].

3. Pertukaran yang Efisien dalam Memori:

   • Penggunaan dekonstruksi ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]) menghilangkan kebutuhan akan variabel sementara, meminimalkan penggunaan memori.

4. Perulangan Minimal:

   • Algoritma hanya menggunakan dua lintasan linier:
     • Satu untuk menyusun ulang array di tempat.
     • Yang lain untuk menemukan bilangan positif pertama yang hilang.

Analisis Kompleksitas:

• Kompleksitas Waktu:
  • Perulangan while dan perulangan for keduanya berjalan dalam $O(n)$, sehingga kompleksitas waktu totalnya adalah $O(n)$.
• Kompleksitas Ruang:
  • Algoritma beroperasi di tempat tanpa menggunakan struktur data tambahan, sehingga kompleksitas ruangnya adalah $O(1)$.

Mengapa Kode Ini Optimal:

• Kinerja: Perulangan while yang disederhanakan memastikan operasi yang berlebihan minimal, memaksimalkan kecepatan.
• Efisiensi Memori: Penggunaan pertukaran di tempat dan penghindaran variabel ekstra memastikan jejak memori serendah mungkin.

Versi 3: Dioptimalkan untuk Memori (Penggunaan Ruang Minimal)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  while (idx < n) {
    const correctIdx = nums[idx] - 1

    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      nums[idx] = nums[correctIdx]
      nums[correctIdx] = correctIdx + 1
    } else {
      idx++
    }
  }

  for (let idx = 0; idx < n; idx++) {
    if (nums[idx] !== idx + 1) {
      return idx + 1
    }
  }

  return nums.length + 1
}

Optimasi Memori Kunci:

1. Pembaruan In-Place dengan Variabel Sementara Minimal:

   • Alih-alih menggunakan variabel temp untuk pertukaran, kode ini langsung memodifikasi array dengan nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1.
   • Ini menghilangkan kebutuhan akan variabel sementara, mengurangi overhead memori dengan jumlah konstan.

2. Nilai Sementara Lebih Sedikit dalam Perulangan:

   • Kode menghitung correctIdx langsung dalam perulangan, menghindari kebutuhan untuk menyimpan variabel antara tambahan di luar logika inti.
   • Lebih sedikit penetapan variabel berarti penggunaan memori sedikit lebih rendah per iterasi.

3. Satu Lintasan untuk Penataan Ulang:

   • Tidak seperti kode pertama yang menggunakan kondisi bersarang dalam perulangan while, implementasi ini menyelesaikan pertukaran atau memajukan indeks dengan cara yang lebih efisien, mengurangi kedalaman tumpukan runtime dan penggunaan memori.
   • Struktur perulangan (while dengan satu peningkatan atau penataan ulang) lebih langsung, membutuhkan lebih sedikit nilai tambahan.

4. Tidak Ada Pemeriksaan Redundan:

   • Pemeriksaan untuk correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx] ringkas dan mencegah operasi yang tidak perlu yang dapat sementara menggunakan memori tumpukan atau cache CPU.
   • Ini menghindari kebutuhan untuk mengalokasikan sumber daya tambahan untuk operasi yang tidak akan berkontribusi pada hasil.

Mengapa Ini Membuat Perbedaan dalam Memori:

• Penyimpanan Sementara Berkurang: Dengan tidak bergantung pada variabel temp dan meminimalkan komputasi antara, jejak memori lebih kecil.
• Eksekusi yang Disederhanakan: Lebih sedikit langkah dan logika yang lebih sederhana diterjemahkan ke penggunaan memori yang lebih sedikit per operasi.
• Pemanfaatan Cache yang Ditingkatkan: Pola akses linier dan dapat diprediksi algoritma meningkatkan kinerja cache CPU, secara tidak langsung mengurangi overhead memori.

Fokus solusi ini pada pembaruan in-place langsung, penggunaan variabel minimal, dan pola akses memori yang efisien menjadikannya yang terbaik dalam hal efisiensi memori. Meskipun penghematannya konstan ($O(1)$), penghematan tersebut cukup signifikan untuk terdaftar pada platform kompetitif seperti LeetCode, terutama untuk dataset besar.

Versi 4: Mahakarya yang Dioptimalkan (Pertukaran In-Place, Tanpa Temp)

function firstMissingPositive(nums: number[]): number {
  for (let i = 0; i < nums.length; i++) {
    while (nums[i] !== i + 1) {
      if (nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]) {
        break
      }

      const temp = nums[i]
      nums[i] = nums[temp - 1]
      nums[temp - 1] = temp
    }
  }

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return nums.length + 1
}

Versi final ini mencapai kinerja optimal dan penggunaan memori minimal melalui pertukaran in-place yang elegan tanpa variabel sementara. Kompleksitas waktunya sekarang tegas $O(n)$, dan kompleksitas ruangnya adalah $O(1)$, memenuhi semua persyaratan. Secara matematis, kita melakukan semacam permutasi siklik dalam array untuk menempatkan elemen pada posisi "benar" mereka.

Dengan menambahkan pemeriksaan (nums[i] === nums[nums[i] - 1]), kita mencegah pertukaran yang tidak perlu. Ini secara signifikan meningkatkan kinerja, membawa kompleksitas waktu lebih dekat ke $O(n)$ yang diinginkan.

Perbedaan Kunci dalam Implementasi:

1. Mencegah Pertukaran yang Redundan:

   • Kode yang diberikan secara eksplisit memeriksa apakah nums[i] === nums[nums[i] - 1] sebelum melakukan pertukaran. Ini menghindari pertukaran yang tidak perlu ketika angka tersebut sudah berada pada posisi yang benar atau duplikat ada.
   • Dalam implementasi pertama, pemeriksaan ini dihilangkan, berpotensi menyebabkan pertukaran yang berlebihan bahkan ketika tidak perlu. Setiap pertukaran tambahan menambah overhead, terutama untuk array yang lebih besar.

2. Perbandingan Indeks Langsung:

   • Kode yang diberikan menggunakan while (nums[i] !== i + 1) untuk memastikan angka tersebut berulang kali ditukar ke posisi yang benar sampai ditempatkan dengan benar atau kondisi tidak valid terpenuhi. Ini menghilangkan iterasi perulangan yang tidak perlu.
   • Kode pertama tidak secara eksplisit membandingkan angka tersebut dengan indeks yang dimaksudkan dalam kondisi perulangan. Ini dapat melakukan lebih banyak operasi dalam kasus di mana angka membutuhkan pergerakan minimal.

3. Pemeriksaan Bersyarat yang Dioptimalkan:

   • Dengan menggabungkan kondisi dalam satu blok if (misalnya, nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]), kode menghindari overhead tambahan dari pemeriksaan atau komputasi yang tidak perlu.

Mengapa Ini Penting di LeetCode:

• Konsistensi Waktu Jalan:

  • Pengukuran waktu jalan LeetCode dapat sensitif terhadap operasi yang tidak perlu, seperti pertukaran yang berlebihan atau perbandingan ekstra.
  • Kode yang diberikan meminimalkan operasi ini, yang mengarah pada waktu jalan yang lebih cepat secara rata-rata.

• Efisiensi Cache:

  • Lebih sedikit pertukaran dan logika perulangan yang lebih sederhana menghasilkan pemanfaatan cache CPU yang lebih baik. Prosesor modern mendapat manfaat dari pola akses yang dapat diprediksi dan efisien, yang ditunjukkan oleh kode yang diberikan.

Hasil

Berikut ringkasan yang disajikan dalam format tabel:

Tabel ini menyoroti trade-off dan optimalitas solusi akhir.

Ringkasan menunjukkan bahwa percobaan untuk kinerja dan memori terbaik memang yang paling optimal, mencapai:

• Waktu jalan 1 ms: Mencocokkan hasil tercepat dalam hal kinerja.
• Penggunaan memori 58,9 MB: Sedikit lebih tinggi daripada klon "memori terbaik" tetapi lebih rendah daripada percobaan lain.

Analisis:

1. Waktu Jalan:

   • Waktu jalan 1 ms menunjukkan pendekatan yang dioptimalkan menghilangkan pemeriksaan yang berlebihan dan pertukaran yang tidak perlu.
   • Kompleksitas waktu yang konsisten dari $O(n)$ memastikan skalabilitas untuk dataset yang lebih besar.

2. Memori:

   • 58,9 MB kompetitif, menunjukkan bahwa jejak memori rendah meskipun eksekusi cepat. Peningkatan sedikit ini dibandingkan dengan "memori terbaik" (58,5 MB) mungkin disebabkan oleh perbedaan dalam dekonstruksi atau optimasi spesifik mesin.

3. Trade-off:

   • Solusi "memori terbaik" sedikit mengorbankan waktu jalan untuk penggunaan memori yang lebih rendah.
   • Solusi "kinerja terbaik" lebih fokus pada kecepatan tetapi menggunakan memori yang sedikit lebih banyak.

Kesimpulan:

Solusi yang dioptimalkan memberikan keseimbangan yang baik:

• Waktu jalan 1 ms secepat kode berkinerja terbaik.
• Penggunaan memori 58,9 MB mendekati hasil memori terbaik, dengan overhead yang dapat diabaikan.

Ini adalah pilihan yang lengkap, terutama untuk skenario di mana kinerja dan memori sama-sama penting.

Dasar Matematika: Permutasi Siklik dan Prinsip Lubang Merpati

Ide intinya berputar di sekitar konsep permutasi siklik. Kita bertujuan untuk membuat siklus di mana setiap angka $x$ ditempatkan pada indeks $x - 1$. Perulangan while secara efektif melintasi siklus ini, memastikan setiap elemen menemukan tempat yang ditentukan.

Prinsip Lubang Merpati secara halus memainkan peran di sini. Karena kita memiliki $n$ posisi yang mungkin (indeks $0$ hingga $n-1$) dan kita mencari bilangan bulat positif yang hilang dalam rentang $[1, n+1]$, jika semua angka dari 1 hingga $n$ ada, angka yang hilang haruslah $n + 1$.

Obsesi Berlanjut...

Ketertarikan saya pada LeetCode 41 tetap ada. Saya terus mencari optimasi lebih lanjut dan wawasan yang lebih dalam. Bergabunglah dengan saya dalam pencarian ini! Bagikan pemikiran Anda, solusi Anda sendiri, dan mari kita jelajahi perpotongan matematika dan algoritma yang elegan bersama-sama.