Twee pointers in een gesorteerde array

De techniek met twee pointers doorloopt een array met twee indices in plaats van geneste lussen. Daardoor worden veel ideeën met O(n^2) omgezet in één overzichtelijke doorgang van O(n). 🎯

De klassieke versie heeft een gesorteerde array nodig. Door de volgorde kun je redeneren: naar rechts gaan vergroot de waarde, naar links gaan verkleint die, dus elke stap is een echte beslissing.

Begin met één pointer aan het linkeruiteinde en één aan het rechteruiteinde. Ze wijzen naar elkaar toe en zullen de afstand ertussen langzaam verkleinen.

Bij elke stap verplaats je precies één pointer naar binnen. De volgorde van de array vertelt je welke kant je moet verschuiven om dichter bij je doel te komen.

Blijf lussen zolang left < right. Wanneer ze elkaar raken of kruisen, is elk nuttig paar gecontroleerd en kun je stoppen.

Bekijk a[left] + a[right] als je huidige kandidaat. Door die met een doelwaarde te vergelijken, weet je of je daarna een grotere of kleinere waarde nodig hebt.

Als de som kleiner is dan de doelwaarde, heb je meer nodig. Verplaats de linkerpointer naar rechts, in de richting van grotere waarden, omdat de array oplopend gesorteerd is.

Als de som groter is dan de doelwaarde, heb je minder nodig. Verplaats de rechterpointer naar links, in de richting van kleinere waarden, om het totaal te verlagen.

Elke verplaatsing elimineert een hele groep paren die je nooit hoeft te testen. Daarom is de doorloop lineair in plaats van kwadratisch.

Je verwerpt alleen paren die niet kunnen overeenkomen, dus het juiste antwoord wordt nooit overgeslagen. Daardoor zijn twee pointers betrouwbaar bij programmeerwedstrijden.

Hetzelfde idee vormt de basis voor varianten: ter plekke omkeren, partitioneren en samenvoegen. Als je de pointers naar elkaar toe leert bewegen, voelen al deze toepassingen vertrouwd.

Met twee pointers doorloop je een gesorteerde array vanaf beide uiteinden en verplaats je bij elke stap één pointer naar binnen zolang left < right. Lineair, correct en de basis voor veel trucs. 🚀