A more efficient way to organize backtracking?

Question

Python

I am writing an algorithm for building a maze based on backtracking. I would like to know how to most effectively implement backtracking so that the algorithm runs faster for very large mazes. The idea is this:
An array of maze cells, where each element is either 0 or 1 - a wall or passage. Initially, all space is walls, in which a passage breaks through in the course of the algorithm. Got stuck? Mark the current cell as a dead end. Next, randomly select a cell with an already dug passage, which is not yet a dead end. We begin to dig a passage from this cell. When all the cells with passages become dead ends, the labyrinth is built. But I don't know which method of choosing a non-dead-end pass is better in terms of search speed. I have 2 ideas:

1) Each element of the array, in addition to the wall / passage state, must store the state of a dead end / not a dead end. Then, when searching for a non-dead-end cell, you will have to select all non-dead-end cells from all existing cells in the space, and only then choose one random one among them. I don't like this method because the total number of space cells can be huge. And each time you have to run through the entire array again in search of non-dead-end elements and select one random one from them.

2) The second approach is to store all cells with passages in a separate array. And leave the array with cell states one-dimensional. When hitting a dead end, it will be necessary to remove the current cell from the array with passes so as not to refer to it next time. As a result, you will have to choose a randomly non-dead-end cell each time among an ever smaller number of cells. But I don't like this approach with a large number of array operations. Dug a new passage - add to the array. We hit a dead end - delete from the array (almost always from somewhere in the middle of the array).
What would you suggest? Maybe some other option?