It is challenging to complete an image whose 99 percent pixels are randomly missing. We present a solution to this extreme image completion problem. As opposed to existing techniques, our solution has a computational complexity that is linear in the number of pixels of the full image and is real-time in practice. For comparable quality of reconstruction, our algorithm is thus almost 2 to 5 orders of magnitude faster than existing techniques.