> I'm not sure we're talking about the same thing. We are. > But you can just write for each cell the index of component it belongs to. It can't belong to man

> I'm not sure we're talking about the same thing. We are. > But you can just write for each cell the index of component it belongs to. It can't belong to many, right? Right. Each cell belongs to 1 and only 1 connected component. However, there can be O(n) connected components overall. Think of a grid of cells all blocked off from each other, for instance. As such, storing which connected component a cell belongs to technically requires O(log n) space, worst-case. Which means have overall you have n cells each requiring O(log n) space, or O(n log n) space overall. In practice you can treat this as effectively O(n), however.