Twee pointers: langzaam en snel

Verplaats alle nullen naar het einde en behoud daarbij de onderlinge volgorde van de niet-nulelementen. De trage pointer markeert de volgende positie voor een niet-nulelement. De snelle pointer zoekt naar niet-nulwaarden. Zodra fast er een vindt, kopieer je die naar de positie van slow en schuif je beide pointers op. Vul na het doorlopen de posities vanaf slow tot het einde met nullen. O(n) tijd, O(1) ruimte.

De partitioneringsstap van quicksort herschikt elementen ter plekke, zodat alle waarden < spilwaarde vóór waarden >= spilwaarde komen. Het schema van Lomuto gebruikt een trage pointer, die de laatste positie van een klein element markeert, en een snelle pointer, die vooruit scant. Wanneer fast een klein element vindt, verhoog je slow en wissel je de elementen om. Dit werkt in O(n) tijd met O(1) extra ruimte.

Met trage en snelle pointers in een gekoppelde lijst gaat de snelle pointer per stap twee knopen vooruit en de trage pointer één. Wanneer fast het einde bereikt, staat slow in het midden. Deze aanpak in één doorgang met O(n) is veel eenvoudiger dan eerst de knopen tellen en daarna tot halverwege lopen. Je gebruikt deze aanpak als deelstap in mergesort voor gekoppelde lijsten en bij het detecteren van palindromen in gekoppelde lijsten.

Bij Floyds cyclusdetectie plaats je de trage en snelle pointers aan het begin van een gekoppelde lijst. Slow gaat één knoop vooruit; fast gaat er twee vooruit. Als er een cyclus bestaat, zal de snelle pointer de trage pointer uiteindelijk inhalen en ontmoeten ze elkaar binnen de cyclus. Als fast None bereikt, is er geen cyclus. De ontmoeting is gegarandeerd omdat fast bij elke iteratie één stap op slow wint — in een cyclus met lengte k ontmoeten ze elkaar binnen k stappen nadat slow de cyclus binnengaat.

Nadat je een cyclus hebt gedetecteerd (slow == fast), zet je één pointer terug naar het begin. Schuif nu beide pointers telkens één stap vooruit. Ze ontmoeten elkaar bij het beginpunt van de cyclus. Dit maakt gebruik van de wiskundige eigenschap dat de afstand van het begin tot het beginpunt van de cyclus gelijk is aan de afstand van het ontmoetingspunt tot het beginpunt van de cyclus, modulo de cycluslengte. Dit is een mooi wiskundig resultaat dat vaak voorkomt in lastige opgaven voor technische sollicitatiegesprekken.

Trage en snelle pointers zijn niet beperkt tot gekoppelde lijsten, maar werken voor elk proces met een cyclus. Een 'geluksgetal' doorloopt cyclisch sommen van kwadraten van cijfers — als n geen geluksgetal is, komt de reeks uiteindelijk in een lus terecht. Detecteer de lus met slow (één stap = één som van cijferkwadraten) en fast (twee stappen). Als ze elkaar bij 1 ontmoeten, is n een geluksgetal; anders zit n vast in een cyclus die niet bij 1 uitkomt. Dit is Floyds algoritme toegepast op een virtuele gekoppelde lijst van waarden.

Vind het n-de element vanaf het einde van een gekoppelde lijst in één doorgang met twee pointers. Schuif de snelle pointer n stappen vooruit. Schuif daarna beide pointers samen op totdat fast het einde bereikt — slow staat nu bij het n-de element vanaf het einde. Houd een pointer met de naam 'prev' één stap achter slow om dit element te verwijderen. Dit is een klassiek probleem met gekoppelde lijsten in één doorgang, waarbij je niet eerst de totale lengte hoeft te tellen.

Het denken in trage en snelle pointers is ook toepasbaar op array- en stringproblemen. Bij het comprimeren van een run-length-gecodeerde string markeert de trage pointer de schrijfpositie en loopt de snelle pointer naar het einde van elke reeks. Als alle tekens in de reeks gelijk zijn aan het teken van slow, schuif je fast op; anders leg je de reeks vast en werk je slow bij. Dit bereikt O(n) in één doorgang met O(1) ruimte.

Gebruik pointers aan tegenovergestelde uiteinden wanneer het probleem gaat over paren met een bepaalde som, palindroomcontroles of het van beide kanten verkleinen van een venster. Gebruik trage en snelle pointers wanneer je een schrijfpositie nodig hebt (elementen verwijderen of verplaatsen), wanneer je de structuur van een gekoppelde lijst verwerkt (midden, cyclus) of wanneer je cycli in een willekeurige waardenreeks detecteert. Beide elimineren geneste lussen en bereiken O(n) — de doorslaggevende factor is de structuur van het doorlopen.

In deze les heb je geleerd dat het trage-en-snelle-patroon (lees-schrijven) een schrijfpositie bij de volgende geldige positie houdt terwijl een snelle pointer vooruit scant — de basis voor ter plekke verwijderen, dedupliceren en nullen verplaatsen, dat Floyds schildpad-en-haasalgoritme cycli detecteert in O(n) tijd en O(1) ruimte door het snelheidsverschil tussen twee pointers te benutten en dat je na het detecteren van een cyclus één pointer terug naar het begin kunt zetten en beide pointers met dezelfde snelheid kunt laten bewegen om het begin van de cyclus te vinden, dankzij een aantoonbare gelijkheid van afstanden. Hierna bekijken we de Python-string-API voor technische sollicitatiegesprekken.