I think we can: 1. Treat every corner as a node. 2. Work out the maximum distance you can travel up, down, left, right from each node by DP from 3. For each 45 degree diagonal in this orientation: \ iterate over nodes on the diagonal from bottom right to top left, treating the current node as the bottom right corner of a target square. Then try to binary search to find the closest top left corner (other node on this diagonal) that can reach nodes reachable by this bottom right corner. I think this essentially requires RMQ on the max up, left, down rights from step 2 and we could use Sparse Table for this. 4. Then we have the smallest square with bottom right corner at X for all nodes X. Then the question is how do you ensure that the squares selected don't contain a "hole". This is where the method comes a bit unstuck because detecting holes is a bit annoying, but I think you can maybe do it by sweeping across the grid L to R and maintaining the current y values with holes. Then you have to try and find in n log n or better which squares need to be discounted due to containing or crossing a hole. I think we could use something like this https://stackoverflow.com/questions/61988883/to-find-if-any-overlapping-rectangles-exist-in-n-number-of-rectangles. But it gets very annoying very quickly.