Short summary: instead of relying on initialization to a known value, ignore the initial values of the array and rely instead on a consistency constraint (data may be random, but won't be random and satisfy the constraint) that you can set and check. A neat trick you can probably use in other places as well.
Anyone know the name of this algorithm? There is a similarly solved classic problem in complexity theory: Given an O(m) list of O(n)-bounded integers, determine if there are duplicates in O(m) time and O(n) space.
I don't know if it has a name (it seems to simply be referred to as "an efficient sparse set representation"), but I think I initially remember seeing it introduced in "Compilers: Principles, Techniques, and Tools" in an exercise at some point in the past.
Comments
Short summary: instead of relying on initialization to a known value, ignore the initial values of the array and rely instead on a consistency constraint (data may be random, but won't be random and satisfy the constraint) that you can set and check. A neat trick you can probably use in other places as well.
Anyone know the name of this algorithm? There is a similarly solved classic problem in complexity theory: Given an O(m) list of O(n)-bounded integers, determine if there are duplicates in O(m) time and O(n) space.
I don't know if it has a name (it seems to simply be referred to as "an efficient sparse set representation"), but I think I initially remember seeing it introduced in "Compilers: Principles, Techniques, and Tools" in an exercise at some point in the past.
A good description of it is here: http://research.swtch.com/2008/03/using-uninitialized-memory...