Check path between first and last rows of randomly updating matrix in O(1) time

Question

We start with a nxn matrix filled with 0s. After each iteration a random cell of the matrix is chosen and changed to a 1. If an already changed cell is chosen again, it remains as a 1 and we proceed to choose a new random cell.

The objective is to determine after each iteration whether a path that connects the first and last rows of the matrix exists in O(1) time.

We define that a path consists of a set of neighbor cells of 1s. Two cells are neighbors if they are at most 1 square away from each other and they both contain a 1. For example, the (i,j)-th cell may have as its neighbor cells the following coordinates: (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j) and (i+1, j+1). In other words, only those cells that surround it may become its neighbors and start forming a path with it.

I know there are algorithms to find such a path for a fixed matrix, but they take at least O(n^2) time. In order to achieve O(1) time I must use information from previous iterations, but so far I have only achieved O(n) time by recursively transversing all possible paths from the last changed cell.

I believe the use of efficient data structures would be suitable to achieve the desired O(1) time, but I'm not too well versed in that matter.

I would gladly appreciate if anyone could sketch an efficient algorithm to achieve this purpose or orientate me in some manner.

Thank you in advance.

Answer 1

In addition to saving whether a cell is "0" or "1", also add information on whether there's a path from the start to that cell. Then, when a new cell is added, you update all potential new neighbors to be visited. While such an update might be O(n) in the worst case (where n is the number of elements which is "1"), it will be amortized O(1) since each cell only gets updated this way once.

record Cell(
    //false if it is "0", else true
    boolean active,
    //if there is a path from the start to this point
    boolean hasPath){}

//just create an empty matrix of cells
private Cell[][] field = createEmptyField(YOUR_N);

private Cell[][] createEmptyField(int n){
    Cell[][] field = new Cell[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            field[i][j]=new Cell(false, false);
        }
    }
    return field;
}

public void fillInRandomlyUntilPath(int startX, int startY, int endX, int endY){
    Random random = ThreadLocalRandom.current();
    field[startX, startY] = new Cell(true, true);//assume the start is visited
    while(!field[endX][endY].hasPath()){//loop until there is a path to the end
        //everything here is amortized O(1)!
        //find new element
        int selectedX = random.nextInt(field.length);
        int selectedY = random.nextInt(field[selectedX].length);
        if(!field[selectedX][selectedY].active()){//if it's already "1", ignore it
            field[selectedX][selectedY] = new Cell(true, false);
            //we need to check all neighbours whether there's a path from the start to any of them
            forAllNeighbours(selectedX, selectedY, (x,y)->{
                if(field[x][y].hasPath()){
                    field[selectedX][selectedY] = new Cell(true, false);
                    setPath(selectedX, selectedY);//if there is a path, check it recursively
                }
            });
        }
    }
}
//this method sets hasPath to true for all neighbours recursively
private void setPath(int x,int y){
    if(field[x][y].active()&&!field[x][y].hasPath()){
        field[x][y]=new Cell(true, true);
        forAllNeighbours(x,y,this::setPath);
    }
}
//execute a function for all neighbours of a point
private void forAllNeighbours(int x, int y, IntBiConsumer exec){
    for(int i=Math.max(0,x-1);i<Math.min(field.length,x+2);i++){
        for(int j=Math.max(0,y-1);j<Math.min(field[i].length,y+2);j++){
            if(x!=i||y!=j){
                exec.accept(i,j);
            }
        }
    }
}

//BiConsumer<Integer,Integer> without boxing
@FunctionalInterface
private static interface IntBiConsumer{
    void accept(int first, int second);
}

If you don't know about amortized complexity, it means that previous calls can take longer than the wished complexity but it will have that complexity on average.

In this case, each cell is only "discovered" once. With discovering, I mean that hasPath is set to true. When that happens, it will check each neighbours which requires 9 (which is a constant) calls but further calls only happen for undiscovered cells. For example, if the cells next to the start are activated last, it would do all the work of discovering the cells at once. However, this work is linear with respect to the number of iterations/activated cells and only needs to be done once.

If you run into StackOverflowErrors (for bigger grids), you might want to change the setPath method to not use recursion.