Finding The Nearest Empty Spot On An Infinite Grid-CodePudding

This was an interview question I have been asked. It involves a 2D grid that consists of empty and occupied spots (0s and 1s if you will) of infinite size. The input contains the coordinates of the occupied spots and it asks me to return the closest empty spot for each occupied spot. You can go through the occupied spots during traversal. This was a free-form coding challenge, it doesn't involve a method signature to begin with.

I am experienced in algorithms and have solved similar problems before, finding the nearest location questions usually involves BFS on the given graph. However, the grid being of infinite size complicated the matter, now that I know I won't be able to store the entire grid on a matrix structure. Nevertheless, I went with BFS method in the end. One problem emerged at this point was how to check whether the current spot is occupied or not. Going through each spot in the input for each visited node doesn't seem like a very good option since it is too slow. So I have suggested that if I can somehow map the occupied spots into a hashmap, then the check operation can be done in constant time. The interviewer told me to assume I have a hash function for the coordinates and my final solution was something like this:

for each occupied spot in the input
    create a queue and push the current spot into the queue
    while queue is not empty
        get the first element from the queue
        if the spot is not occupied and not marked
            add the spot into result list and break the while loop
        else if spot is not marked
            push its neighbors into queue and mark it

The outer for loop takes O(n) time for each spot in the input. The BFS algorithm runs in O(v e), the interviewer suggested that it can be represented as a constant factor of n as O(cn). My final algorithm runs in O(n^2).

As you can expect I failed the interview, otherwise I wouldn't be posting this question. Can you point me to my mistakes? I thought the interview went well and couldn't find anything on the internet search on how to solve the question on an infinite grid. Maybe I should have started by clarifying how to store an infinite grid but couldn't think at that moment.

CodePudding user response：

I'm guessing that what they wanted you to do was loop in a spiral with the center starting from each known occupied spot. So something like:

Distance = 1;
foreach(occupiedSpace)
{
occupied = true; // my own position is occupied by definition
While (!occupied) // loop in a spiral and check for an open space
{
 for(possibleXPosition = -1* distance   occupiedSpace.x to distance   occupiedSpace.x)
    for(possibleYPosition = (-1) distance   occupiedSpace.y to distance   occupiedSpace.y ){
    occupied = check( array[possibleXPosition, possibleYPosition])
    if(!occupied){ 
    output.print(closest position to (occupiedSpace is possibleXPosition, 
                 possibleYPosition)
}
}
  
distance  ;
}}

There are some real implementations here: Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin

CodePudding user response：

Look at LeetCode #286 Walls and Gates. This is a variation of the BFS solution to that problem.

However, instead of adding gates when you initialize the queue, you would be adding occupied spots that are next to an unoccupied spot to it. You would be starting BFS at once from every one of those spots.

Hope this hint helps.