Two pointers to jeden z najczęstszych wzorców algorytmicznych na rozmowie technicznej. Większość zadań typu „znajdź parę o sumie X w sorted array", „sprawdź czy string to palindrom", „wykryj cykl w linked list" albo „dedup posortowanej listy" sprowadza się do prostego pomysłu: dwa wskaźniki poruszające się po tej samej strukturze.
W tym artykule pokazuję trzy warianty: opposite-direction (dwa wskaźniki idące do siebie z końców), same-direction (slow + fast iteruje w tym samym kierunku, write/read), fast/slow (Floyd's tortoise-and-hare dla cykli i środkowego elementu). Każdy z trace step-by-step i sygnałami rozpoznawczymi. Implementacje w Pythonie dla zwięzłości — wzorzec jest language-agnostic.
Pozostaję w obrębie czystego two pointers. Sliding window (też z dwoma wskaźnikami, ale z dynamicznie rozciąganym oknem) to powiązany ale osobny temat.
Czym jest two pointers — definicja + ASCII
Two pointers, czyli technika dwóch wskaźników, to sposób rozwiązywania problemu przez utrzymywanie dwóch pozycji w tej samej strukturze danych: najczęściej dwóch indeksów w tablicy lub stringu, czasem dwóch referencji do węzłów listy. To nie muszą być prawdziwe wskaźniki pamięci w sensie niskopoziomowym; w Pythonie będą to zwykle indeksy albo zmienne trzymające obiekty. Sam termin „pointer” ma źródło w klasycznym programowaniu, gdzie oznacza referencję do miejsca w pamięci, co opisuje m.in. Wikipedia.
Intuicja jest prosta: zamiast sprawdzać wszystkie pary elementów, przesuwasz dwa wskaźniki tak, aby każdy ruch odrzucał część przestrzeni możliwych odpowiedzi. W wariancie opposite-direction działa to najlepiej na danych posortowanych, bo porządek mówi, czy trzeba zwiększyć, czy zmniejszyć aktualną wartość.
sorted nums: [1, 2, 4, 7, 11, 15]
L R
sum too small -> move L right
sum too large -> move R left
after moves: [1, 2, 4, 7, 11, 15]
L R
Spotkasz ten wzorzec, gdy zadanie mówi o parach, symetrii, deduplikacji, partycjonowaniu, cyklu w liście albo pracy „in place”. Sygnałem ostrzegawczym jest brute force O(n²) dla par w tablicy, zwłaszcza gdy dane są posortowane albo można je posortować bez utraty sensu problemu.
def has_pair_sum(nums, target):
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == target:
return True
if total < target:
left += 1
else:
right -= 1
return False
print(has_pair_sum([1, 2, 4, 7, 11, 15], 15)) # expected_output: True
Pułapka: użycie opposite-direction na nieposortowanej tablicy. Dla inputu [8, 1, 7, 2], target 9, para istnieje: 1 + 8. Jeśli ustawisz left=0, right=3, dostajesz 8 + 2 = 10 i przesuwasz right, zakładając, że suma spadnie w kontrolowany sposób. Ale bez sortowania ten ruch nie ma gwarancji: po lewej i prawej nie ma monotonicznego porządku, więc algorytm może odrzucić poprawną parę.
Wariant 1: opposite-direction
Opposite-direction to wariant, w którym jeden wskaźnik startuje na początku, drugi na końcu, a oba poruszają się ku sobie. Typowy szablon to left = 0, right = n - 1, pętla while left < right. Ten wariant jest naturalny dla posortowanych tablic i problemów symetrycznych, takich jak palindrome.
Działa dzięki temu, że skrajne elementy niosą informację o całym pozostałym zakresie. W posortowanej tablicy przesunięcie lewego wskaźnika w prawo zwykle zwiększa wartość, a przesunięcie prawego w lewo zwykle ją zmniejsza. To pozwala wykonać lokalną decyzję bez utraty globalnej poprawności.
nums: [1, 3, 4, 6, 8, 10]
L R
1 + 10 = 11
if target is 14:
move L -> sum gets larger
nums: [1, 3, 4, 6, 8, 10]
L R
3 + 10 = 13
Rozpoznasz go po zadaniach typu „znajdź parę”, „sprawdź, czy dwa końce pasują”, „maksymalizuj/minimalizuj coś z dwóch krańców”. Jeżeli w treści pojawia się sorted array, sorted string, pair, closest pair, palindrome albo partition, najpierw sprawdź, czy da się kontrolować ruch dwóch końców.
def closest_pair_sum(nums, target):
left, right = 0, len(nums) - 1
best = None
while left < right:
total = nums[left] + nums[right]
if best is None or abs(target - total) < abs(target - best):
best = total
if total < target:
left += 1
else:
right -= 1
return best
print(closest_pair_sum([1, 3, 4, 6, 8, 10], 14)) # expected_output: 14
Krok 1: ustaw left na najmniejszy element, right na największy. Krok 2: policz wynik z pary skrajnych elementów. Krok 3: jeśli wynik jest za mały, przesuń left, bo tylko większy lewy element może pomóc. Krok 4: jeśli wynik jest za duży, przesuń right, bo tylko mniejszy prawy element może pomóc. Krok 5: kończysz, gdy wskaźniki się spotkają.
Pułapka: warunek pętli left <= right przy szukaniu pary dwóch różnych elementów. Dla [1, 2, 3], target 4, po ruchach możesz dojść do left == right == 1 i policzyć 2 + 2, choć ten sam element nie może być użyty dwa razy. Mechanizm błędu jest prosty: <= pozwala wskaźnikom wskazać tę samą pozycję, więc algorytm produkuje parę, której nie ma w danych.
Two Sum sorted
Two Sum sorted to najczystszy przykład opposite-direction. Masz posortowaną tablicę i target, a celem jest znalezienie dwóch liczb o zadanej sumie. Wersja z hashem działa w O(n) czasie, ale potrzebuje O(n) pamięci. Wersja two pointers też działa w O(n) czasie, ale zużywa O(1) dodatkowej pamięci, bo trzyma tylko dwa indeksy. To klasyka znana m.in. z LeetCode Two Sum II.
Intuicja: jeśli nums[left] + nums[right] jest za małe, to przesunięcie right w lewo tylko zmniejszy albo utrzyma sumę, więc nie pomoże. Musisz przesunąć left w prawo. Jeśli suma jest za duża, analogicznie przesuwasz right w lewo. Porządek tablicy zamienia zgadywanie w deterministyczne odrzucanie kandydatów.
target = 13
[1, 2, 4, 6, 9, 11]
L R sum=12 -> move L
L R sum=13 -> found
Spotkasz to w rozmowie jako pytanie wprost albo jako część większego problemu: „find pair in sorted array”, „return indices”, „closest two sum”, „count pairs”. Jeżeli interviewer podkreśla, że input jest posortowany, to prawie zawsze jest to wskazówka, aby nie zaczynać od hash mapy.
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == target:
return [left, right]
if total < target:
left += 1
else:
right -= 1
return [-1, -1]
print(two_sum_sorted([1, 2, 4, 6, 9, 11], 13)) # expected_output: [1, 5]
Krok 1: left=0, right=5, suma 1+11=12, za mało. Krok 2: przesuwasz left na 1, bo potrzebujesz większej sumy. Krok 3: suma 2+11=13, target znaleziony. Krok 4: zwracasz indeksy [1, 5]. Nie sprawdzasz par (1,4), (1,6), (1,9) osobno, bo monotoniczność już powiedziała, które kierunki są bez sensu.
Pułapka: sortowanie tablicy, gdy masz zwrócić oryginalne indeksy. Dla nums=[10, 1, 7, 2], target 9, po sortowaniu dostajesz [1, 2, 7, 10] i para ma indeksy [1, 2] w posortowanej kopii, ale w oryginale to indeksy [1, 2] tylko przypadkiem. Dla innych danych wynik będzie błędny. Jeśli musisz sortować, sortuj pary (value, original_index).
Walidacja palindromu
Walidacja palindromu to drugi ważny przykład opposite-direction, ale tutaj nie potrzebujesz sortowania. Potrzebujesz symetrii: pierwszy istotny znak ma odpowiadać ostatniemu istotnemu znakowi, drugi przedostatniemu itd. W praktycznych zadaniach rekrutacyjnych trzeba zwykle pominąć znaki non-alphanumeric i porównać obie strony po zamianie na lowercase. Metody str.isalnum() i str.lower() są częścią standardowej biblioteki Pythona, opisanej w docs.python.org.
Intuicja jest lustrzana. Wskaźniki idą z dwóch stron, ale zatrzymują się tylko na znakach, które biorą udział w porównaniu. Jeżeli litery po normalizacji różnią się, cały string nie jest palindromem. Jeżeli pasują, przesuwasz oba końce do środka.
"A man, a plan, a canal: Panama"
L R
A a equal after lowercase
L R
m m equal
Sygnał rozpoznawczy: „ignore spaces”, „ignore punctuation”, „case-insensitive”, „valid palindrome”. To dobry moment, aby nie budować od razu oczyszczonego stringa, jeśli możesz rozwiązać problem w O(1) dodatkowej pamięci przez skanowanie z dwóch stron.
def is_valid_palindrome(text):
left, right = 0, len(text) - 1
while left < right:
while left < right and not text[left].isalnum():
left += 1
while left < right and not text[right].isalnum():
right -= 1
if text[left].lower() != text[right].lower():
return False
left += 1
right -= 1
return True
print(is_valid_palindrome("A man, a plan, a canal: Panama")) # expected_output: True
Krok 1: left trafia na A, right na a; po lowercase są równe. Krok 2: pomijasz spacje, przecinki i dwukropek, bo isalnum() zwraca dla nich False. Krok 3: porównujesz kolejne pary znaków po lowercase. Krok 4: gdy wskaźniki się miną albo spotkają, wszystkie pary przeszły test, więc wynik to True.
Pułapka: porównywanie znaków przed pominięciem separatorów. Dla "ab,a" błędny kod porówna a z a, potem b z , i zwróci False. Mechanizm: przecinek nie jest częścią logicznego tekstu, ale został potraktowany jak znak porównywalny. Najpierw przesuwasz wskaźniki przez znaki niealfanumeryczne, dopiero potem robisz lowercase i porównanie.
Wariant 2: same-direction
Same-direction to wariant, w którym oba wskaźniki idą w tę samą stronę. Jeden zwykle czyta dane (read, fast), a drugi wskazuje miejsce zapisu albo granicę poprawnego prefiksu (write, slow). Ten wariant wymaga sekwencyjnego dostępu i często działa in place: bez dodatkowej tablicy, bez hasha, bez kopiowania całego inputu.
Intuicja przypomina edycję tekstu w miejscu. read przegląda każdy element dokładnie raz, a write przesuwa się tylko wtedy, gdy element ma zostać zachowany. W deduplikacji posortowanej tablicy porządek gwarantuje, że duplikaty stoją obok siebie, więc wystarczy porównać aktualny element z ostatnim zapisanym.
nums: [1, 1, 2, 2, 3]
W
R -> duplicate, skip
R -> new value, write at W+1
after: [1, 2, 3, 2, 3]
W
Spotkasz ten wariant w zadaniach „remove duplicates from sorted array”, „remove element”, „move zeros”, „partition array”. Jeśli treść mówi, że masz zmodyfikować tablicę w miejscu i zwrócić nową długość, to prawie zawsze chodzi o write/read.
def remove_duplicates(nums):
if not nums:
return 0
write = 1
for read in range(1, len(nums)):
if nums[read] != nums[write - 1]:
nums[write] = nums[read]
write += 1
return write
data = [1, 1, 2, 2, 3]
print(remove_duplicates(data), data[:3]) # expected_output: 3 [1, 2, 3]
Krok 1: write=1, bo pierwszy element jest już poprawnym prefiksem. Krok 2: read=1, widzisz drugie 1, czyli duplikat ostatniego zapisanego elementu; nic nie zapisujesz. Krok 3: read=2, widzisz 2, zapisujesz pod write=1. Krok 4: kolejne 2 pomijasz. Krok 5: 3 zapisujesz pod write=2. Wynikowa długość to 3.
Pułapka: porównywanie nums[read] z nums[read - 1] zamiast z nums[write - 1] w wariantach, gdzie dozwolona liczba kopii jest większa niż jedna albo warunek zachowania jest bardziej złożony. Mechanizm błędu: read - 1 opisuje surowy input, a write - 1 opisuje wynik budowany in place. Gdy te dwa światy się rozjadą, zaczynasz porównywać z elementem, który nie jest ostatnim zaakceptowanym elementem.
Wariant 3: fast/slow tortoise-hare
Fast/slow, znany jako tortoise-hare, używa dwóch referencji poruszających się z różną prędkością. slow robi jeden krok, fast robi dwa. W linked list pozwala to wykryć cykl bez dodatkowej pamięci. Jeśli cykl istnieje, wskaźniki w końcu się spotkają. Jeśli cyklu nie ma, fast dojdzie do None.
Intuicja jest geometryczna: w acyklicznej liście szybszy wskaźnik po prostu dotrze do końca. W cyklu szybszy wskaźnik zaczyna „doganiać” wolniejszy na zamkniętej pętli. Różnica dystansu między nimi zmienia się o jeden krok na iterację, więc przy skończonej długości cyklu musi kiedyś wynieść zero modulo długość cyklu.
A -> B -> C -> D -> E
^ |
|_________|
slow: one step
fast: two steps
inside cycle, fast eventually reaches slow
Spotkasz ten wariant przy „detect cycle”, „find middle of linked list”, „happy number” i czasem przy wykrywaniu powtórzeń w strukturach, które da się interpretować jako przejścia. To nie jest wariant od sortowania; tu kluczowe jest to, że da się iść sekwencyjnie po relacji next.
class Node:
def __init__(self, value):
self.value = value
self.next = None
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
a, b, c = Node(1), Node(2), Node(3)
a.next, b.next, c.next = b, c, b
print(has_cycle(a)) # expected_output: True
Krok 1: slow i fast startują na głowie listy. Krok 2: slow przechodzi do następnego węzła, fast przeskakuje o dwa. Krok 3: jeśli lista ma koniec, fast albo fast.next stanie się None. Krok 4: jeśli lista ma cykl, oba wskaźniki trafią do tej samej pętli. Krok 5: gdy slow is fast, wykrywasz cykl.
Pułapka: sprawdzanie while fast.next bez sprawdzenia fast. Dla pustej listy albo dla listy o parzystej długości bez cyklu fast może stać się None, a następna próba odczytu fast.next kończy się wyjątkiem. Mechanizm błędu: warunek pętli sam dereferencjuje obiekt, którego istnienia jeszcze nie potwierdziłeś. Poprawna kolejność to while fast and fast.next.
Three Sum
Three Sum to rozszerzenie Two Sum: szukasz trójek liczb, które sumują się do zera albo do targetu. Klasyczne rozwiązanie sortuje tablicę, wybiera jeden element w zewnętrznej pętli, a dla pozostałego zakresu uruchamia inner two pointers. Całość działa w O(n²) zamiast naiwnego O(n³), bo dla każdego i robisz liniowe przejście left/right. To jedno z najbardziej rozpoznawalnych pytań z LeetCode 3Sum.
Intuicja: po ustaleniu pierwszej liczby problem redukuje się do Two Sum sorted. Jeśli nums[i] + nums[left] + nums[right] jest za małe, przesuwasz left. Jeśli za duże, przesuwasz right. Sortowanie daje monotoniczność, a pomijanie duplikatów daje unikalne trójki.
nums sorted: [-4, -1, -1, 0, 1, 2]
i L R
fixed i = -1
need pair sum = 1
move L/R like Two Sum sorted
Spotkasz to jako „return all unique triplets”, „sum of three numbers”, „closest three sum”. Jeżeli brute force ma trzy pętle, a sortowanie nie niszczy odpowiedzi, naturalnym ruchem jest zredukowanie jednej pętli przez two pointers.
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
elif total < 0:
left += 1
else:
right -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4])) # expected_output: [[-1, -1, 2], [-1, 0, 1]]
Krok 1: sortujesz do [-4, -1, -1, 0, 1, 2]. Krok 2: wybierasz i=-4, szukasz pary 4, nie znajdujesz. Krok 3: wybierasz pierwsze -1, left i right znajdują [-1, -1, 2]. Krok 4: przesuwasz oba wskaźniki i pomijasz duplikaty po lewej. Krok 5: znajdujesz [-1, 0, 1]. Krok 6: drugie -1 jako i pomijasz, bo dałoby te same trójki.
Pułapka: brak pomijania duplikatów dla i. Dla [-1, -1, 0, 1] algorytm bez continue zwróci [-1, 0, 1] dwa razy: raz dla pierwszego -1, raz dla drugiego. Mechanizm: po sortowaniu równe wartości tworzą identyczne przestrzenie wyszukiwania, więc powtarzasz tę samą pracę i produkujesz duplikaty wyniku.
Sygnały rozpoznawcze: kiedy two pointers
Two pointers wybierasz wtedy, gdy problem ma liniowy porządek i decyzja o ruchu jednego wskaźnika coś gwarantuje. W opposite-direction zwykle potrzebujesz posortowanych danych albo symetrii. W same-direction potrzebujesz sekwencyjnego dostępu i możliwości budowania poprawnego prefiksu. W fast/slow potrzebujesz relacji następnego kroku, jak next w linked list.
Intuicja rozpoznawania polega na pytaniu: „czy jeden ruch usuwa całą klasę kandydatów?”. Jeśli tak, two pointers ma sens. Jeśli nie, dwa indeksy będą tylko ozdobą nad brute force. Dobre sygnały to: sorted array, pair sum, palindrome, dedup sorted, remove element, move zeros, partition, linked list cycle, middle of list.
pair in sorted data:
smallest ---------------- largest
L R
in-place filter:
accepted prefix | unknown suffix
W R -> scans forward
cycle:
slow moves 1, fast moves 2
Na rozmowie rekrutacyjnej warto powiedzieć głośno, która własność pozwala przesuwać wskaźnik. Dla Two Sum sorted: monotoniczność sumy. Dla palindromu: symetria. Dla dedup sorted: duplikaty są sąsiadami. Dla cycle detection: różnica prędkości w cyklu musi doprowadzić do spotkania.
def remove_element(nums, value):
write = 0
for read in range(len(nums)):
if nums[read] != value:
nums[write] = nums[read]
write += 1
return write
data = [3, 2, 2, 3, 4]
print(remove_element(data, 3), data[:3]) # expected_output: 3 [2, 2, 4]
Krok 1: read przechodzi po każdym elemencie. Krok 2: gdy element jest równy usuwanej wartości, nie robisz nic. Krok 3: gdy element ma zostać, kopiujesz go na pozycję write. Krok 4: write zawsze oznacza długość poprawnego prefiksu. Krok 5: elementy za write są nieistotne, bo kontrakt zadania zwykle każe zwrócić nową długość.
Pułapka: wymuszanie two pointers, gdy brakuje własności porządku. Dla „znajdź dwie liczby o sumie target w dowolnej, niesortowanej tablicy i zwróć oryginalne indeksy” lepszy bywa hash map. Jeśli posortujesz, tracisz indeksy albo musisz nosić je osobno. Jeśli nie posortujesz, ruch left/right nie mówi nic o przyszłych sumach.
Kiedy NIE two pointers
Nie używaj two pointers, gdy problem nie ma porządku, symetrii, sekwencyjnego filtra ani relacji next, która daje sens różnym prędkościom. Dwa wskaźniki same w sobie nie są algorytmem; są narzędziem do wykorzystania struktury danych. Jeśli input jest losowy, warunek zależy od wielu niezależnych kryteriów, a ruch jednego indeksu nie eliminuje kandydatów, technika nie daje przewagi.
Intuicja anty-przykładu: masz tablicę obiektów, a para ma spełniać jednocześnie warunek po cenie, kategorii, dacie i uprawnieniach użytkownika. Sortowanie po cenie może pomóc dla ceny, ale zepsuje albo ukryje pozostałe kryteria. Ruch left lub right nie ma już jednej interpretacji. Wtedy częściej potrzebujesz mapy, indeksu, sortowania po wielu kluczach, drzewa, kopca albo pełnego przeglądu kandydatów.
random records:
[{price, tag, date}, {price, tag, date}, ...]
sort by price?
L and R can reason about price only.
They cannot guarantee tag/date/permission correctness.
Sygnał, że to nie ten wzorzec: po każdej próbie zapisania reguły ruchu masz zdanie „to zależy”. Jeśli suma za mała, ale kategoria zła, data za późna, a element po lewej ma inne uprawnienia, nie wiesz, który wskaźnik przesunąć. Brak deterministycznej reguły ruchu oznacza brak realnego two pointers.
def two_sum_unsorted(nums, target):
seen = {}
for index, value in enumerate(nums):
missing = target - value
if missing in seen:
return [seen[missing], index]
seen[value] = index
return [-1, -1]
print(two_sum_unsorted([8, 1, 7, 2], 9)) # expected_output: [0, 1]
Krok 1: widzisz 8, zapamiętujesz indeks 0. Krok 2: widzisz 1, liczysz brakującą wartość 8. Krok 3: 8 jest już w mapie, więc zwracasz oryginalne indeksy. To jest dobry przykład, gdzie hash map z O(n) pamięci jest prostszy i stabilniejszy niż udawanie opposite-direction bez sortowania.
Pułapka: sortowanie danych, gdy wynik zależy od oryginalnej kolejności. Dla inputu [8, 1, 7, 2], target 9, posortowana tablica daje pary wartości, ale nie odpowiada już bezpośrednio pozycjom z wejścia. Mechanizm błędu: operacja przygotowawcza zmienia informację, którą masz zwrócić. Two pointers byłby poprawny dopiero po zachowaniu par (value, original_index) albo gdy zadanie pyta wyłącznie o wartości, nie o indeksy.
Najczęstsze błędy
Two pointers na nieposortowanej tablicy (opposite-direction). Algorytm zakłada że nums[left] + nums[right] < target implikuje „cel po prawej". Bez sortowania ta logika załamuje się, bo następny element może być mniejszy. Mechanizm błędu: dla [3, 1, 5, 2] z target=4 wskaźniki nie znajdą pary (1, 3) bo nie idą sekwencyjnie. Naprawa: sorted(nums) przed two pointers, albo użyj hash mapy (O(n) bez pre-sort).
Brak < w warunku while left < right. Pętla while left <= right powoduje że left i right mogą się spotkać na tym samym elemencie i dostaniesz fałszywą parę (nums[i] + nums[i]) lub nieskończoną pętlę. Mechanizm: gdy oba wskaźniki na indeksie i, total może równać target przez przypadek. Naprawa: zawsze while left < right dla opposite-direction.
Brak skipowania duplikatów w Three Sum. Wewnętrzne while left < right and nums[left] == nums[left+1]: left += 1 jest niezbędne, inaczej [(0, 0, 0), (0, 0, 0), (0, 0, 0)] (duplikaty w wyniku). Mechanizm błędu: po znalezieniu trójki, jeśli następny element jest taki sam, znajdziesz tę samą trójkę. Naprawa: po result.append(...) przesuń wskaźniki PRZED następną iteracją tak, żeby ominąć równe wartości.
Slow/fast bez sprawdzania fast.next. W Floyd's algorithm fast = fast.next.next rzuca AttributeError gdy fast lub fast.next jest None. Mechanizm błędu: lista bez cyklu kończy się, ale algorytm próbuje skoku o 2 — drugi .next na None. Naprawa: warunek pętli while fast and fast.next przed każdym podwójnym skokiem.
Same-direction bez aktualizacji write pointer po pomyłce. Wzorzec write/read dla dedup: if nums[read] != nums[write]: write += 1; nums[write] = nums[read]. Łatwo pomylić kolejność — najpierw inkrement write, potem assign. Mechanizm błędu: kolejność daje albo overwrite ważnego elementu, albo missed slot. Naprawa: write zaczyna od 0, pierwsze pisanie na write+1 po znalezieniu różnego elementu.
FAQ
Czy two pointers wymaga posortowanych danych?
Zależy od wariantu. Opposite-direction (Two Sum sorted, palindrom) zwykle wymaga sortowania, bo porządek decyduje o ruchu wskaźników. Same-direction (dedup, partition) działa na nieposortowanej tablicy, bo logika jest sekwencyjna. Fast/slow (cycle detection) operuje na linked list bez założenia o porządku wartości.
Two Sum z hash mapą czy two pointers — który lepszy?
Hash map: O(n) czas, O(n) extra space, działa na nieposortowanej tablicy. Two pointers: O(n) czas po O(n log n) sortowaniu, O(1) extra space, wymaga sorted. Hash wybierasz gdy nie chcesz mutować tablicy lub gdy lookup w hashu jest tańszy. Two pointers wybierasz gdy pamięć krytyczna lub tablica już sortowana. Szczegóły: Haszowanie w Zadaniach.
Floyd's algorithm — dlaczego fast skacze o 2, nie o 3?
Bo kombinacja kroków slow=1, fast=2 gwarantuje że jeśli istnieje cykl, wskaźniki spotkają się w nim w skończonym czasie. Z fast=3 matematyka się komplikuje (dłuższe okresy spotkania). Krok 2 jest minimalnym, który gwarantuje detekcję — fast=2*slow speed. Algorytm pochodzi od Roberta Floyda, choć przypisywanie autorstwa jest sporne (czasem nazywany cycle finding bez nazwiska).
Czy two pointers może mieć więcej niż dwa wskaźniki?
Tak — wzorzec rozszerza się na trzy lub więcej wskaźników. Three Sum używa zewnętrznej pętli + dwóch wskaźników. Cztery wskaźniki dla 4-Sum. Generalnie: każdy dodatkowy wskaźnik to potencjalnie dodatkowy rząd n w złożoności (O(n²) dla three sum, O(n³) dla 4-sum).
Co z linked list bez random access — czy two pointers działa?
Tak, ale tylko same-direction (oba wskaźniki idą .next). Opposite-direction wymaga O(1) losowego dostępu do końca, co linked list nie oferuje (O(n) żeby dotrzeć do tail). Klasyczne use cases linked list two pointers: cycle detection (slow/fast), middle element (slow=1, fast=2 → gdy fast dochodzi do końca, slow jest w środku), n-th from end (advance one by n, then move both).
Three Sum z O(n^2) to optymum?
Tak dla comparison-based. Lower bound dla 3-sum to Ω(n²) w modelu porównań. Można zbliżyć się do O(n²) z hash setem zamiast wewnętrznych two pointers, ale stałe są gorsze. Two pointers + sort jest standardową odpowiedzią na rozmowie. Szczegóły asymptotyki: Big O w 10 minut.
Powiązane tematy
- Haszowanie w Zadaniach — Wzorzec na Rozmowie — alternatywa dla Two Sum (
O(n)czas +O(n)pamięć vsO(n log n)sort +O(1)); porównaj sygnały rozpoznawcze. - Wyszukiwanie Binarne — Dziel-i-Zwyciężaj — kolejna technika
O(log n)na sorted array; complementary do opposite-direction two pointers. - Big O w 10 Minut — Notacja Złożoności — kontekst dla
O(n)two pointers vsO(n²)brute force iO(n³)naive Three Sum.
Sprawdź swoją wiedzę quizem
Przerób ten artykuł w 15-pytaniowy quiz testujący opposite vs same-direction, Two Sum sorted, palindrom, cycle detection i Three Sum: https://odpytywarka.pl/q/O99tvm.
Masz własne notatki na rozmowę? Wgraj PDF lub wklej tekst na stworz-quiz-z-pdf — pierwsze 3 strony PDF i 15 pytań jednokrotnego wyboru za darmo, generowanie 30-60 sekund.
Źródła
- Pointer (computer programming) — Wikipedia — definicja referencji jako podstawy two pointers
- Cycle detection — Wikipedia — Floyd's tortoise-and-hare algorithm
- Python
bisectmodule — alternatywa dla two pointers w sorted array - Big O notation — Wikipedia — formal definition złożoności