Analiza

Primetimo da je ~K <= 1000000~, pa ukoliko mi možemo da u ~O(1)~ proverimo da li su svi brojevi jednaki nekom broju u istom pravougaoniku, mi možemo rešiti zadatak u ~O(K)~, što je složenost koja je dovoljno dobra. Ukoliko posmatramo sve vrednosti koje su jednake nekom broju ~A~, jedini kandidat za dobar pravougaonik koji sadrži samo brojeve ~A~ je najmanji pravougaonik koji sadrži sve njih (ukoliko bi bio neki veći, sigurno bi postojao broj koji nije jednak tom broju, ukoliko bi bio neki manji, postojao bi broj jednak tom broju koji nije u njemu). Sada, provera da li je taj pravouganik dobar je ekvivalentna proveri da li je površina tog pravougaonika jednaka broju pojavljivanja broja ~A~ u matrici (zato što svako pojavljivanje tog broja mora biti u tom pravougaoniku).

Smernice za algoritam

Prvo, želimo da unapred izračunamo, za svaki broj, koji je njegov odgovorajući pravougaonik. On će se prostirati od najmanjeg reda u kom postoji taj broj do najvećeg, i od najmanje kolone u kojoj postoji taj broj, do najveće. Takođe, možemo izračunati i broj pojavljivanja svakog broja. Onda, jednom petljom, idemo po svih brojevima od ~1~ do ~K~ i proveravamo da li je kandidat pravouganik dobar, u ~O(1)~. Što se tiče složenosti, treba nam ~O(N^2)~ za preprocesiranje, i ~O(K)~ za sve provere, tako da je ukupna složenost ~O(N^2 + K)~.