 <p>For 8 and 16 bit it's pretty obvious, you can track every possibility every iteration.</p> <p>When you get to 32 and 64 bit integers, you don't really have the memory to track every possibility.</p> <p>Here's a few natural suggestions that are likely outside the bounds of your constraints.</p> <p>I don't really understand why you can't sort the array. RadixSort is O(n) and once sorted it would be one more pass to get accurate distinctiveness and top X information. In reality it would be 6 passes all together for 32bit if you used a 1 byte radix (1 pass for counting + 1 * 4 passes for each byte + 1 pass for getting values).</p> <p><strong>In the same cusp as above, why not just use SQL. You could create a stored procedure that takes the array in as a table valued parameter and return the number of distinct values and the top x values in one go. This stored procedure could also be called in parallel.</strong></p> <pre><code>-- number of distinct SELECT COUNT(DISTINCT(n)) FROM @tmp -- top x SELECT TOP 10 n, COUNT(n) FROM @tmp GROUP BY n ORDER BY COUNT(n) DESC </code></pre>