Analiza

Potrebno je naći sve elemente niza ~A~ koji se pojavljuju bar ~K~ puta u nizu. Elementi niza ~A~ su u intervalu ~[-N,N]~ tako da postoji ~2 \cdot N+1~ različitih vrednosti koje se mogu pojaviti u nizu. Možemo iskoristiti pomoćni niz ~B~ dužine ~2 \cdot N+1~ koji predstavlja broj pojavljivanja svakog elementa u početnom nizu.

Na početku niz ~B~ ima vrednost ~0~ na svakoj poziciji. Jednim prolaskom kroz niz ~A~, kada naiđeimo na element ~A_i~ povećavamo broj pojavljivanja tog elementa za ~1~. Pošto ne možemo pristupiti negativnim indeksima broj pojavljivanja elementa koji ima vrednost ~X~ pamtimo u nizu ~B~ na poziciji ~X+N~. Tako je interval ~[-N,N]~ preslikan u interval ~[0, 2 \cdot N]~ što nam omogućava da koristimo niz.

Prolaskom kroz niz ~B~ prebrojavamo i ispisujemo sve brojeve koji su se pojavili bar ~K~ puta u nizu. Ako za neko ~j~ važi da je ~B[j] \geq K~ to znači da se broj ~j-N~ pojavio bar ~K~ puta.

Implementacija korišćenjem niza je složenosti ~O(N)~. Može se koristiti i struktura zasnovana na pretraživačkom stablu (std::map složenosti ~O(N \log N)~) ili heš tabela (std::unordered_map očekivane složenosti ~O(N)~) što nam omogućava rešenje i kada su elementi niza ~A~ mnogo veliki i nemamo dovoljno memorije da napravimo niz koji obuhvata sve potencijalne vrednosti.