Ang Aking LeetCode 41 Obsession: Isang Malalimang Pagsusuri sa First Missing Positive Puzzle

Ang problema sa LeetCode na "First Missing Positive" (numero 41) ang naging pinakabagong obsesyon ko sa pagko-coding. Isang nakaliligaw na simpleng palaisipan ito na sumasakop sa aking isipan, na nagtutulak sa akin na tuklasin ang mga detalye nito at lumikha ng pinaka-epektibong solusyon sa TypeScript na posible. Ang post na ito ay hindi lamang tungkol sa pag-aayos ng mga coding interview (kahit na iyon ay isang magandang karagdagan). Ito ay tungkol sa dalisay na kasiyahan ng paglutas ng problema, ang kapanapanabik na pakiramdam ng optimization, at ang eleganteng kagandahan ng mahusay na code. At dahil medyo mahilig ako sa matematika, susuriin pa natin ang mga pundasyon ng matematika ng solusyon.

Ang Problema: Isang Lobo na Nakasuot ng Balat ng Tupa

Ang problema ay nagpapakita ng isang unsorted array ng mga integer. Ang iyong gawain: hanapin ang pinakamaliit na nawawalang positive integer. Mukhang madali? Pag-isipan muli. Ang mga constraints ng $O(n)$ na oras at $O(1)$ na space complexity ay nagbabago sa tila simpleng gawain na ito sa isang mahirap na algorithmic puzzle.

Unang Paghihirap: Ang Bitag ng Brute Force

Ang aking unang mga pagtatangka ay may kasamang pag-aayos (lumalabag sa $O(n)$ na constraint sa oras) at hash sets (lumampas sa $O(1)$ na limitasyon sa espasyo). Malinaw, kailangan ng mas sopistikadong approach.

Ang Eureka Moment: In-Place Transformation

Ang pangunahing pananaw ay ang pag-realize na magagamit ko ang input array mismo bilang isang hash table. Sa pamamagitan ng muling pag-aayos ng mga elemento, mailalagay ko ang numero $x$ sa index $x - 1$ (kung $1 \le x \le n$, kung saan ang $n$ ay ang haba ng array). Ang in-place transformation na ito ay nagbubukas ng daan patungo sa isang mahusay na solusyon.

Ebolusyon ng Code: Isang Saga ng TypeScript

Narito ang talaan ng ebolusyon ng aking code, na may detalyadong mga paliwanag at mga pananaw sa matematika:

Bersyon 1: Ang Naive Approach (na may Redundant Swaps)

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

  // Ilagay ang bawat numero sa tamang posisyon nito kung nasa range [1, n] ito
  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]] // Palitan
    }
  }

  // Hanapin ang unang nawawalang positive
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // Kung ang lahat ng numero ay nasa tamang posisyon na nila, ang nawawalang numero ay n + 1
  return n + 1
}

Ang bersyong ito, kahit na gumagana, ay may mga redundant swaps. Ang bilang ng mga swaps sa worst-case scenario ay umaabot sa $O(n^2)$, bagaman ang average case ay mas malapit sa $O(n)$.

Paliwanag:

1. Muling ayusin ang array: Ang bawat numero nums[i] ay inilalagay sa "tamang" index nito (nums[i] - 1) kung ito ay nasa range [1, n] at hindi pa nasa tamang posisyon.

2. Tukuyin ang nawawalang positive: Pagkatapos ng muling pag-aayos, ang unang index i kung saan nums[i] !== i + 1 ay nagpapahiwatig na ang i + 1 ay ang nawawalang positive integer.

3. Ibalik ang n + 1 kung kinakailangan: Kung ang lahat ng numero mula 1 hanggang n ay nasa tamang posisyon na, ang nawawalang numero ay n + 1.

Mga Pangunahing Punto:

• In-place rearrangement: Binabago natin ang array mismo upang maiwasan ang paggamit ng dagdag na espasyo.
• Kahusayan: Parehong ang rearrangement at ang final scan ay tumatagal ng $O(n)$ na oras, tinitiyak ang pinakamainam na performance.

Bersyon 2: Pagpapalakas ng Performance (Pag-aalis ng Redundant Swaps)

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

  // Muling ayusin ang mga numero sa kanilang tamang posisyon kung posible
  while (idx < n) {
    const correctIdx = nums[idx] - 1
    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      // Palitan nang hindi gumagamit ng temporary variable
      ;[nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]
    } else {
      idx++
    }
  }

  // Tukuyin ang unang nawawalang positive
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return n + 1
}

Paliwanag:

1. Mahusay na Rearrangement:

   • Ang while loop ay direktang nagpapalit ng mga elemento sa kanilang tamang posisyon (nums[idx] - 1) lamang kapag ang numero ay nasa valid range [1, n] at hindi pa nasa tamang posisyon.
   • Ang if condition ay tinitiyak na ang mga invalid o tama na ang posisyon ay tinatalo nang walang hindi kinakailangang mga palitan.

2. Direktang Pagsusuri ng Index:

   • Sa panahon ng rearrangement phase, ang mga invalid swaps at redundant operations ay iniiwasan sa pamamagitan ng pagsusuri sa range at value ng nums[idx].

3. Memory-Efficient Swapping:

   • Ang paggamit ng destructuring ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]) ay inaalis ang pangangailangan para sa isang temporary variable, binabawasan ang paggamit ng memory.

4. Minimal na Loops:

   • Ang algorithm ay gumagamit lamang ng dalawang linear passes:
     • Isa para muling ayusin ang array in place.
     • Isa pa para hanapin ang unang nawawalang positive.

Pagsusuri ng Complexity:

• Time Complexity:
  • Ang while loop at ang for loop ay parehong tumatakbo sa $O(n)$, ginagawa ang total time complexity na $O(n)$.
• Space Complexity:
  • Ang algorithm ay gumagana in-place nang hindi gumagamit ng anumang auxiliary data structures, kaya ang space complexity ay $O(1)$.

Kung Bakit Optimal ang Code na Ito:

• Performance: Ang streamlined while loop ay tinitiyak ang minimal na redundant operations, pinapataas ang bilis.
• Kahusayan sa Memory: Ang paggamit ng in-place swapping at pag-iwas sa mga dagdag na variable ay tinitiyak ang pinakamababang posibleng memory footprint.

Bersyon 3: Ang In-optimize para sa Memory (Minimal na Paggamit ng Espasyo)

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
}

Mga Pangunahing Optimization sa Memory:

1. In-Place Updates na may Minimal na Temporary Variables:

   • Sa halip na gumamit ng temp variable para sa swapping, ang code na ito ay direktang binabago ang array gamit ang nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1.
   • Inaalis nito ang pangangailangan para sa isang temporary variable, binabawasan ang memory overhead ng isang constant amount.

2. Mas Kaunting Temporary Values sa Loop:

   • Ang code ay direktang kinakalkula ang correctIdx sa loop, iniiwasan ang pangangailangan na mag-imbak ng karagdagang mga intermediate variable sa labas ng core logic.
   • Ang mas kaunting mga variable assignments ay nangangahulugan ng bahagyang mas mababang paggamit ng memory bawat iteration.

3. Single Pass para sa Rearrangement:

   • Hindi tulad ng unang code na gumagamit ng nested conditions sa while loop, ang implementasyong ito ay nakukumpleto ang mga swaps o ina-advance ang index sa isang mas streamlined na paraan, binabawasan ang runtime stack depth at paggamit ng memory.
   • Ang loop structure (while na may isang solong increment o rearrangement) ay mas direkta, nangangailangan ng mas kaunting mga auxiliary values.

4. Walang Redundant Checks:

   • Ang mga pagsusuri para sa correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx] ay maigsi at pumipigil sa mga hindi kinakailangang operasyon na maaaring pansamantalang gumamit ng stack o CPU cache memory.
   • Iniiwasan nito ang pangangailangan na maglaan ng dagdag na resources para sa mga operasyon na hindi makakatulong sa resulta.

Kung Bakit Gumagawa Ito ng Pagkakaiba sa Memory:

• Nabawasan ang Pansamantalang Imbakan: Sa pamamagitan ng hindi pag-asa sa isang temp variable at pagbabawas ng mga intermediate computations, ang memory footprint ay mas maliit.
• Streamlined na Pagpapatupad: Ang mas kaunting mga hakbang at simpleng logic ay nagreresulta sa mas kaunting paggamit ng memory bawat operasyon.
• Pinahusay na Paggamit ng Cache: Ang linear, predictable access pattern ng algorithm ay nagpapabuti sa performance ng CPU cache, hindi direktang binabawasan ang memory overhead.

Ang pokus ng solusyong ito sa direktang in-place updates, minimal na paggamit ng variable, at mahusay na mga pattern ng pag-access sa memory ay ginagawa itong pinakamahusay sa mga tuntunin ng kahusayan ng memory. Habang ang mga savings ay constant ($O(1)$), ang mga ito ay sapat na makabuluhan upang magrehistro sa mga competitive platform tulad ng LeetCode, lalo na para sa mga malalaking datasets.

Bersyon 4: Ang In-optimize na Masterpiece (In-Place Swapping, Walang 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
}

Ang pangwakas na bersyon na ito ay nakakamit ang parehong pinakamainam na performance at minimal na paggamit ng memory sa pamamagitan ng eleganteng in-place swapping nang walang temporary variable. Ang time complexity ay ngayon ay matatag na $O(n)$, at ang space complexity ay $O(1)$, tinutupad ang lahat ng mga kinakailangan. Sa matematika, gumagawa tayo ng isang uri ng cyclic permutation sa loob ng array upang ilagay ang mga elemento sa kanilang "tamang" posisyon.

Sa pamamagitan ng pagdaragdag ng isang check (nums[i] === nums[nums[i] - 1]), pinipigilan natin ang mga hindi kinakailangang swaps. Makabuluhang pinapataas nito ang performance, na ginagawa ang time complexity na mas malapit sa nais na $O(n)$.

Mga Pangunahing Pagkakaiba sa Implementation:

1. Pag-iwas sa Redundant Swaps:

   • Ang ibinigay na code ay tahasang sinusuri kung nums[i] === nums[nums[i] - 1] bago isagawa ang swap. Iniiwasan nito ang mga hindi kinakailangang swaps kapag ang numero ay nasa tamang posisyon na o may mga duplicate.
   • Sa unang implementation, ang check na ito ay tinanggal, na maaaring humantong sa redundant swaps kahit na hindi kinakailangan. Ang bawat karagdagang swap ay nagdaragdag ng overhead, lalo na para sa mas malalaking arrays.

2. Direktang Paghahambing ng Index:

   • Ang ibinigay na code ay gumagamit ng while (nums[i] !== i + 1) upang matiyak na ang isang numero ay paulit-ulit na pinapalitan sa tamang posisyon nito hanggang sa ito ay mailagay nang tama o matugunan ang isang invalid na kondisyon. Inaalis nito ang mga hindi kinakailangang loop iterations.
   • Ang unang code ay hindi tahasang inihahambing ang numero sa nilalayong index nito sa loob ng loop condition. Maaaring magsagawa ito ng higit pang mga operasyon sa mga kaso kung saan ang mga numero ay nangangailangan ng minimal na paggalaw.

3. In-optimize na Conditional Checks:

   • Sa pamamagitan ng pagsasama-sama ng mga kondisyon sa isang solong if block (hal., nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]), iniiwasan ng code ang karagdagang overhead mula sa mga hindi kinakailangang pagsusuri o computations.

Kung Bakit Mahalaga Ito sa LeetCode:

• Pagkakapare-pareho ng Runtime:

  • Ang mga sukat ng runtime ng LeetCode ay maaaring sensitibo sa mga hindi kinakailangang operasyon, tulad ng redundant swaps o extra comparisons.
  • Binabawasan ng ibinigay na code ang mga operasyong ito, na humahantong sa mas mabilis na runtime sa average.

• Kahusayan ng Cache:

  • Ang mas kaunting swaps at simpleng loop logic ay nagreresulta sa mas mahusay na paggamit ng CPU cache. Ang mga modernong processor ay nakikinabang mula sa predictable at streamlined na mga pattern ng access, na ipinapakita ng ibinigay na code.

Resulta

Narito ang buod na iniharap sa format ng talahanayan:

Binibigyang-diin ng talahanayang ito ang mga trade-off at ang optimality ng pangwakas na solusyon.

Ipinapahiwatig ng buod na ang pagtatangkang para sa pinakamahusay na performance at memory ay talagang ang pinaka-optimize, na nakakamit:

• 1 ms runtime: Tumutugma sa pinakamabilis na resulta sa mga tuntunin ng performance.
• 58.9 MB memory usage: Bahagyang mas mataas kaysa sa "pinakamahusay na memory" na clone ngunit mas mababa kaysa sa ibang mga pagtatangka.

Pagsusuri:

1. Runtime:

   • Ang 1 ms runtime ay nagpapakita na ang in-optimize na approach ay inaalis ang redundant checks at hindi kinakailangang swaps.
   • Ang pare-parehong time complexity ng $O(n)$ ay tinitiyak ang scalability para sa mas malalaking datasets.

2. Memory:

   • Ang 58.9 MB ay mapagkumpitensya, na nagpapakita na ang memory footprint ay mababa sa kabila ng mabilis na pagpapatupad. Ang bahagyang pagtaas na ito sa "pinakamahusay na memory" (58.5 MB) ay maaaring dahil sa mga pagkakaiba sa destructuring o mga engine-specific na optimization.

3. Trade-offs:

   • Ang "pinakamahusay na memory" na solusyon ay bahagyang sinasakripisyo ang runtime para sa mas mababang paggamit ng memory.
   • Ang "pinakamahusay na performance" na solusyon ay mas nakatuon sa bilis ngunit gumagamit ng bahagyang mas maraming memory.

Konklusyon:

Ang in-optimize na solusyon ay may magandang balanse:

• Ang 1 ms runtime ay kasing bilis ng pinakamahusay na gumaganang code.
• Ang 58.9 MB memory usage ay malapit sa pinakamahusay na resulta ng memory, na may bale-wala na overhead.

Ito ay isang well-rounded na pagpipilian, lalo na para sa mga sitwasyon kung saan ang parehong performance at memory ay mahalaga.

Mga Pundasyon ng Matematika: Cyclic Permutations at Pigeonhole Principle

Ang pangunahing ideya ay umiikot sa konsepto ng cyclic permutations. Nilalayon naming lumikha ng isang cycle kung saan ang bawat numero $x$ ay inilalagay sa index $x - 1$. Ang while loop ay epektibong tumatakbo sa mga cycle na ito, tinitiyak na ang bawat elemento ay nakahanap ng itinakdang lugar nito.

Ang Pigeonhole Principle ay banayad na gumaganap ng isang papel dito. Dahil mayroon tayong $n$ na posibleng mga posisyon (indices $0$ hanggang $n-1$) at hinahanap natin ang isang nawawalang positive integer sa loob ng range $[1, n+1]$, kung ang lahat ng mga numero mula 1 hanggang $n$ ay naroroon, ang nawawalang numero ay dapat na $n + 1$.

Ang Obsesyon ay Nagpapatuloy...

Ang aking pagkahumaling sa LeetCode 41 ay nananatili. Patuloy akong naghahanap ng karagdagang mga optimization at mas malalim na mga pananaw. Sumali sa akin sa paghahanap na ito! Ibahagi ang iyong mga saloobin, ang iyong sariling mga solusyon, at tuklasin natin ang eleganteng intersection ng matematika at mga algorithm nang sama-sama.