3 ms·
Using a sparse bit-array will reduce the memory space of the problem.
by sangupta 10y ago
Using a sparse bit-array will reduce the memory space of the problem.
- rhardih 10y agoYes, but do you have an implementation of a sparse array with constant time lookups?
- sangupta 10y agoI can work up one. Choosing the right bucket will be O(1) as the index is integer. We can store the buckets for lookup in a hash-table or an array-of-arrays, which again will be O(1). Reaching to the actual index should again be O(1) - unless am messing something here.