I remember Mario Paint on Super Nintendo visibly flood-filling an area, but a computer that paints in modern image formats is probably not going to mind temporary allocation of a few hundred K. There are some fun opportunities to optimize, though, like checking a cache line of pixels at a time, or maybe tiling the image in 16-pixel squares using the same algorithm, and then cleaning up the edges.

The author of the submitted article has written about working in constrained environments. The algorithm he describes would be suitable for that kind of environment, where a few hundred K may not be available, or not without jumping through hoops to make it available.

https://t3x.org/#wyorc - One example, this is a book on writing a compiler targeting Z80 processors.