Zadanie. Dany jest ciąg  rzutów monetą. Należy sprawdzić, jaka jest najdłuższa seria kolejnych rzutów, w której wypadło dokładnie  razy więcej orłów niż reszek. Dla przykładu, w ciągu

serie od piątego do dwunastego, jak również od szóstego do trzynastego rzutu zawierają dokładnie 6 orłów i 2 reszki. Zatem dla  odpowiedzią jest 8, gdyż nie istnieje żadna dłuższa seria zawierająca dokładnie 3 razy więcej orłów niż reszek.

Uprośćmy na chwilę nasze zadanie i powiedzmy, że chcemy znaleźć najdłuższą serię spełniającą warunki zadania, która zawiera pierwszy rzut. Użyjemy dwóch zmiennych  i  oznaczających liczby reszek i orłów, które wypadły do tej pory. Za każdym razem, kiedy po rzucie wystąpi  będzie to oznaczało, że znaleźliśmy dłuższą serię. Zauważmy jednak, że nie potrzebujemy aż dwóch zmiennych: nie interesuje nas dokładna liczba orłów i reszek, a jedynie ich wzajemne zbilansowanie. Możemy więc trzymać jeden licznik  który po każdym rzucie będziemy uaktualniali następująco: wyrzucenie reszki zwiększa  o  natomiast wyrzucenie orła zmniejsza  o  Oznaczmy przez  wartość licznika po -tym rzucie (przyjmujemy też ). Teraz każde  odpowiada poprawnej serii kończącej się -tym rzutem.

A co w ogólnym przypadku? Zastanówmy się, jaki warunek musi być spełniony, aby pewna seria spełniająca warunki zadania kończyła się -tym rzutem monetą. Łatwo przekonać się, że jest tak wtedy, gdy istnieje taki rzut  że wartość licznika po -tym rzucie jest taka sama jak po -tym rzucie ( ) – wtedy rzuty od -ego do  -tego tworzą poprawną serię. Chcielibyśmy zatem dla danego  szybko stwierdzać, jaki jest (o ile istnieje) najmniejszy numer rzutu  dla którego  Skorzystamy w tym celu z drzewa wyszukiwań binarnych, w którym dla klucza  będziemy trzymać odpowiadający mu numer rzutu. Teraz po -tym rzucie, jeśli klucz  występuje w drzewie z wartością  to zgłaszamy znalezienie serii o długości   W przeciwnym przypadku uaktualniamy drzewo, wstawiając do niego klucz  z wartością  Zauważmy, że jeśli w drzewie istniał już klucz  to nie musieliśmy go uaktualniać, gdyż interesuje nas jedynie najmniejszy numer rzutu odpowiadający temu kluczowi. Każda operacja na drzewie zajmuje czas  zatem całe rozwiązanie działa w czasie

Czytelnicy, którzy słyszeli o tablicach haszujących, mogą powiedzieć, że bez kłopotu uzyskalibyśmy rozwiązanie działające w oczekiwanym czasie  gdybyśmy zamiast drzewa wyszukiwań binarnych użyli właśnie tablicy haszującej. To prawda, ale okazuje się, że można jeszcze lepiej – wykorzystując specyfikę naszego zadania, można zaprojektować „tablicę haszującą”, która da nam rozwiązanie  i to w pesymistycznym przypadku!

Zamiast drzewa będziemy mieli tablicę Odwołania do klucza  będą realizowane przez komórkę  w której będziemy trzymać listę par postaci (klucz  numer rzutu). Innymi słowy, po -tym rzucie sprawdzamy, czy na liście  znajduje się para  dla pewnego  Jeśli tak, to zgłaszamy znalezienie serii o długości   a w przeciwnym przypadku uaktualniamy listę  wstawiając do niej nową parę

I teraz czas na kluczową obserwację. Załóżmy, że nastąpił drugi z powyższych przypadków. To oznacza, że na liście  mogą znajdować się tylko pary  gdzie  dla  Zauważmy jednak, że ilekroć nasz licznik osiągnął pewną wartość  to w przyszłości już nigdy nie będzie równy  lub mniejszy, ponieważ po każdym rzucie możemy go zmniejszyć co najwyżej o  Zatem na liście nie ma żadnej pary dla  (bo wtedy byłoby  co przeczy temu, że aktualna wartość licznika to ). Co więcej, skoro pary, które mogą pojawić się na liście, spełniają  to sytuacja, w której licznik byłby równy  nigdy już nie wystąpi. Tak więc przed dodaniem pary  do listy  możemy z niej usunąć wszystkie występujące na niej pary. Widać zatem, że na żadnej liście nie będzie nigdy więcej niż jednej pary – stąd czas wyszukiwania na liście faktycznie będzie stały.