### bilew89378's blog

By bilew89378, history, 6 weeks ago,

hi folks

someone posted a question that got me curious if this is solvable, none of blind lurkers have been able to solve this. asking for algo experts to chip in from cf community

Question: "given 100K points within coordinate system, find the coordinates of smallest square that contains cluster of at least 15% of all points"

It seems Petr was interviewer for this candidate as only he can solve this in < 45 minute

• +13

 » 6 weeks ago, # | ← Rev. 3 →   +6 I think this can be solved using binary search on the size of square. When the size of square is fixed, you can iterate on the $x$ coordinate, rejecting points with $x-k$ coordinates. Maintain the $y$ coordinates in a set and just just check how many points are in the set with y-coordinate less than or equal to current y-coordinate (by Fenwick tree/ ordered-set). Time complexity will be $O(nlog(n)log(c)$, where $c$ is the maximum coordinate.