3 ms·

So what is the trick?

• lalaland1125 9y ago
  The trick is that you only need to store the unordered list of seen integers as your state while you sort. This takes about 1.5MB or so. The reduction in space comes from the fact that you don't have to store the order (for example, you could store the numbers sorted and only record offsets. That saves space because the offsets will be smaller)
• _wmd 9y ago
  It's the opening problem from Programming Pearls: http://www.fusu.us/2013/06/bitmap-sort.html http://www.fusu.us/2013/06/bitmap-sort.html (edit: better link)
  • sirclueless 9y ago
    How is this relevant? A bitmap of size 2^32 is 512MB in size and you only have 2MB of memory.