Moja opsesija s LeetCode 41: Duboko zaranjanje u zagonetku prvog nedostajućeg pozitivnog broja

LeetCodeov problem "Prvi nedostajući pozitivni broj" (broj 41) postao je moja posljednja programska opsesija. To je obmanjujuće jednostavna zagonetka koja mi je zauzela misli, tjerajući me da istražim njene zamršenosti i kreiramo što efikasnije moguće rješenje u TypeScriptu. Ovaj post nije samo o uspjehu na programerskim intervjuima (iako je to lijep bonus). Radi se o čistoj radosti rješavanja problema, uzbuđenju optimizacije i elegantnoj ljepoti efikasnog koda. I pošto sam malo matematički zaljubljenik, čak ćemo se pozabaviti i matematičkim osnovama rješenja.

Problem: Vuk u ovčijoj koži

Problem predstavlja neuređen niz cijelih brojeva. Vaš zadatak: pronađite najmanji nedostajući pozitivni cijeli broj. Čini se jednostavnim? Razmislite ponovo. Ograničenja vremena $O(n)$ i prostornog $O(1)$ kompleksnosti pretvaraju ovaj naizgled jednostavan zadatak u izazovnu algoritamsku zagonetku.

Početne muke: Zamka grube sile

Moji početni pokušaji uključivali su sortiranje (kršenje vremenskog ograničenja $O(n)$) i hash skupove (prelaženje prostornog ograničenja $O(1)$). Jasno je da je bio potreban sofisticiraniji pristup.

Eureka trenutak: Transformacija na mjestu

Ključni uvid bio je shvatiti da mogu koristiti sam ulazni niz kao hash tablicu. Preuređivanjem elemenata, mogu postaviti broj $x$ na indeks $x - 1$ (ako je $1 \le x \le n$, gdje je $n$ dužina niza). Ova transformacija na mjestu otključava put do efikasnog rješenja.

Evolucija koda: TypeScript saga

Evo hronologije evolucije mog koda, sa detaljnim objašnjenjima i matematičkim uvidima:

Verzija 1: Naivni pristup (sa redundantnim zamjenama)

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

  // Postavite svaki broj na svoju pravilnu poziciju ako je u rasponu [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]] // Zamjena
    }
  }

  // Pronađite prvi nedostajući pozitivni broj
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // Ako su svi brojevi na svojim pravilnim pozicijama, nedostajući broj je n + 1
  return n + 1
}

Ova verzija, iako funkcionalna, pati od redundantnih zamjena. Broj zamjena u najgorem slučaju pristupa $O(n^2)$, iako je prosječni slučaj bliži $O(n)$.

Objašnjenje:

1. Preuredite niz: Svaki broj nums[i] se postavlja na svoj "ispravan" indeks (nums[i] - 1) ako je u rasponu [1, n] i nije već na ispravnoj poziciji.

2. Identifikujte nedostajući pozitivni broj: Nakon preuređivanja, prvi indeks i gdje je nums[i] !== i + 1 ukazuje da je i + 1 nedostajući pozitivni cijeli broj.

3. Vratite n + 1 ako je potrebno: Ako su svi brojevi od 1 do n na ispravnim pozicijama, nedostajući broj je n + 1.

Ključne tačke:

• Preuređivanje na mjestu: Modificiramo sam niz kako bismo izbjegli korištenje dodatnog prostora.
• Efikasnost: I preuređivanje i konačno skeniranje traju $O(n)$ vremena, osiguravajući optimalne performanse.

Verzija 2: Povećanje performansi (eliminacija redundantnih zamjena)

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

  // Preuredite brojeve na njihove ispravne pozicije ako je moguće
  while (idx < n) {
    const correctIdx = nums[idx] - 1
    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      // Zamjena bez korištenja privremene varijable
      ;[nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]
    } else {
      idx++
    }
  }

  // Identifikujte prvi nedostajući pozitivni broj
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return n + 1
}

Objašnjenje:

1. Efikasno preuređivanje:

   • Petlja while direktno zamjenjuje elemente na njihove ispravne pozicije (nums[idx] - 1) samo kada je broj u validnom rasponu [1, n] i nije već na ispravnoj poziciji.
   • Uslov if osigurava da se nevalidne ili već ispravne brojeve preskoče bez nepotrebnih zamjena.

2. Direktna provjera indeksa:

   • Tokom faze preuređivanja, nevalidne zamjene i redundantne operacije se izbjegavaju provjerom raspona i vrijednosti nums[idx].

3. Memorija-efikasna zamjena:

   • Korištenje dekonstruiranja ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]) eliminira potrebu za privremenom varijablom, minimizirajući korištenje memorije.

4. Minimalne petlje:

   • Algoritam koristi samo dva linearna prolaza:
     • Jedan za preuređivanje niza na mjestu.
     • Drugi za pronalaženje prvog nedostajućeg pozitivnog broja.

Analiza složenosti:

• Vremenska složenost:
  • Petlja while i petlja for obje rade u $O(n)$, čineći ukupnu vremensku složenost $O(n)$.
• Prostornu složenost:
  • Algoritam radi na mjestu bez korištenja dodatnih pomoćnih struktura podataka, tako da je prostorna složenost $O(1)$.

Zašto je ovaj kod optimalan:

• Performanse: Pojednostavljena petlja while osigurava minimalne redundantne operacije, maksimizirajući brzinu.
• Efikasnost memorije: Korištenje zamjene na mjestu i izbjegavanje dodatnih varijabli osigurava najmanji mogući memorijski otisak.

Verzija 3: Optimizirano za memoriju (minimalna upotreba prostora)

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
}

Ključne optimizacije memorije:

1. Ažuriranja na mjestu sa minimalnim privremenim varijablama:

   • Umjesto korištenja temp varijable za zamjenu, ovaj kod direktno modificira niz sa nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1.
   • Ovo eliminira potrebu za privremenom varijablom, smanjujući memorijski overhead za konstantnu količinu.

2. Manje privremenih vrijednosti u petlji:

   • Kod izračunava correctIdx direktno u petlji, izbjegavajući potrebu za pohranjivanjem dodatnih intermedijarnih varijabli izvan glavne logike.
   • Manje dodjela varijabli znači nešto nižu potrošnju memorije po iteraciji.

3. Jedan prolaz za preuređivanje:

   • Za razliku od prvog koda koji koristi uvježbane uvjete u petlji while, ova implementacija dovršava zamjene ili napreduje indeks na strujniji način, smanjujući dubinu steka za vrijeme izvođenja i potrošnju memorije.
   • Struktura petlje (while sa jednim povećanjem ili preuređivanjem) je direktnija, zahtijevajući manje pomoćnih vrijednosti.

4. Nema redundantnih provjera:

   • Provjere za correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx] su koncizne i sprječavaju nepotrebne operacije koje bi privremeno mogle koristiti memoriju steka ili CPU keša.
   • Ovo izbjegava potrebu za dodjeljivanjem dodatnih resursa za operacije koje neće doprinijeti rezultatu.

Zašto ovo pravi razliku u memoriji:

• Smanjeno privremeno skladištenje: Neslanjanjem na temp varijablu i minimiziranjem intermedijarnih izračuna, memorijski otisak je manji.
• Pojednostavljeno izvršenje: Manje koraka i jednostavnija logika prevode se u manju potrošnju memorije po operaciji.
• Poboljšano korištenje keša: Linearan, predvidljiv obrazac pristupa algoritma poboljšava performanse CPU keša, indirektno smanjujući memorijski overhead.

Ovaj fokus rješenja na direktna ažuriranja na mjestu, minimalnu upotrebu varijabli i efikasne obrasce pristupa memoriji čini ga najboljim u smislu efikasnosti memorije. Iako su uštede konstantne ($O(1)$), dovoljno su značajne da se registriraju na konkurentnim platformama kao što je LeetCode, posebno za velike skupove podataka.

Verzija 4: Optimizirani remek-djelo (zamjena na mjestu, bez 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
}

Ova konačna verzija postiže i optimalne performanse i minimalnu potrošnju memorije kroz elegantnu zamjenu na mjestu bez privremene varijable. Vremenska složenost je sada čvrsto $O(n)$, a prostorna složenost je $O(1)$, ispunjavajući sve zahtjeve. Matematički, izvodimo vrstu ciklične permutacije unutar niza kako bismo postavili elemente na njihove "ispravne" pozicije.

Dodavanjem provjere (nums[i] === nums[nums[i] - 1]), sprječavamo nepotrebne zamjene. Ovo značajno poboljšava performanse, približavajući vremensku složenost željenom $O(n)$.

Ključne razlike u implementaciji:

1. Izbjegavanje redundantnih zamjena:

   • Dati kod eksplicitno provjerava da li je nums[i] === nums[nums[i] - 1] prije izvođenja zamjene. Ovo izbjegava nepotrebne zamjene kada je broj već na ispravnoj poziciji ili postoje duplikati.
   • U prvoj implementaciji, ova provjera je izostavljena, što potencijalno dovodi do redundantnih zamjena čak i kada nisu potrebne. Svaka dodatna zamjena dodaje overhead, posebno za veće nizove.

2. Direktna usporedba indeksa:

   • Dati kod koristi while (nums[i] !== i + 1) kako bi se osiguralo da se broj više puta zamijeni na svoju ispravnu poziciju dok se ne postavi ispravno ili se ne ispuni nevažeći uvjet. Ovo eliminira nepotrebne iteracije petlje.
   • Prvi kod ne uspoređuje eksplicitno broj sa svojim predviđenim indeksom unutar uvjeta petlje. Može izvesti više operacija u slučajevima kada brojevi trebaju minimalno pomjeranje.

3. Optimizirane uvjetne provjere:

   • Kombiniranjem uvjeta u jedan blok if (npr. nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]), kod izbjegava dodatni overhead od nepotrebnih provjera ili izračuna.

Zašto je ovo važno na LeetCode-u:

• Dosljednost vremena izvođenja:

  • LeetCode-ova mjerenja vremena izvođenja mogu biti osjetljiva na nepotrebne operacije, kao što su redundantne zamjene ili dodatne usporedbe.
  • Dati kod minimizira ove operacije, što dovodi do bržeg vremena izvođenja u prosjeku.

• Efikasnost keša:

  • Manje zamjena i jednostavnija logika petlje rezultiraju boljim korištenjem CPU keša. Moderni procesori imaju koristi od predvidljivih i pojednostavljenih obrazaca pristupa, koje dati kod pokazuje.

Rezultati

Evo sažetka predstavljenog u tabelarnom formatu:

Ova tabela ističe kompromise i optimalnost konačnog rješenja.

Sažetak ukazuje da je pokušaj za najbolje performanse i memoriju doista najoptimiziraniji, postižući:

• 1 ms vrijeme izvođenja: Podudaranje s najbržim rezultatom u smislu performansi.
• 58.9 MB upotreba memorije: Nešto više od klona "najbolje memorije", ali niže od drugih pokušaja.

Analiza:

1. Vrijeme izvođenja:

   • 1 ms vrijeme izvođenja pokazuje da optimizirani pristup eliminira redundantne provjere i nepotrebne zamjene.
   • Dosljedna vremenska složenost od $O(n)$ osigurava skalabilnost za veće skupove podataka.

2. Memorija:

   • 58.9 MB je konkurentno, pokazujući da je memorijski otisak nizak uprkos brzom izvršavanju. Ovo malo povećanje u odnosu na "najbolju memoriju" (58.5 MB) može biti zbog razlika u dekonstruiranju ili optimizacijama specifičnim za motor.

3. Kompromisi:

   • Rješenje "najbolje memorije" malo žrtvuje vrijeme izvođenja za nižu potrošnju memorije.
   • Rješenje "najboljih performansi" više se fokusira na brzinu, ali koristi malo više memorije.

Zaključak:

Optimizirano rješenje postiže dobru ravnotežu:

• 1 ms vrijeme izvođenja je jednako brzo kao i kod najboljih performansi.
• 58.9 MB upotreba memorije je blizu rezultata "najbolje memorije", sa zanemarivim overheadom.

To je dobro zaokružen izbor, posebno za scenarije u kojima su i performanse i memorija kritične.

Matematičke osnove: Ciklične permutacije i princip golubarnika

Osnovna ideja se vrti oko koncepta cikličnih permutacija. Cilj nam je stvoriti ciklus gdje je svaki broj $x$ postavljen na indeks $x - 1$. Petlja while efikasno prolazi kroz ove cikluse, osiguravajući da svaki element pronađe svoju određenu poziciju.

Princip golubarnika suptilno igra ulogu ovdje. Pošto imamo $n$ mogućih pozicija (indeksi $0$ do $n-1$) i tražimo nedostajući pozitivni cijeli broj u rasponu $[1, n+1]$, ako su svi brojevi od 1 do $n$ prisutni, nedostajući broj mora biti $n + 1$.

Opsesija se nastavlja...

Moja fascinacija LeetCode 41 ostaje. Stalno tražim daljnje optimizacije i dublje uvide. Pridružite mi se u ovoj potrazi! Podijelite svoje misli, svoja rješenja i istražimo elegantno sjecište matematike i algoritama zajedno.