The classic Roombas from a decade or so ago worked without any sort of mapping or camera at all -- they basically did a version of the "run and tumble" algorithm used by many bacteria -- go in one direction until you can't any more then go off in a random new one. It may not be efficient but it does work for covering territory.
I think the only reason for mapping is to be able to block off 'no go' areas (no escaping out the front door!) and to be able to go home to the charger.
For the actual cleaning, random works great.
Surely mapping also helps reducing the time it takes to achieve the task?
You are right. The original Roomba was discussed on HN 3 months ago:
https://news.ycombinator.com/item?id=46472930