Group numbers with the same digits

Question

Given a list of positive integers, group together all numbers that use exactly the same multiset of digits (same digits, any order).

nums = [12, 21, 122, 212, 221, 3]
-> [[12, 21], [122, 212, 221], [3]]

Return the groups (any order). Aim for better than the $O(n^2)$ all-pairs comparison.

Accepted Answer

Two numbers are digit-permutations of each other exactly when their digits, sorted, are identical. So map each number to a canonical form, the sorted string of its digits, and bucket by that key in a hash map. On the example the keys are 12, 12, 122, 122, 122, 3, producing the three groups shown. With n numbers of up to d digits, sorting each key costs O(n\, d \log d) total. To drop the log factor, use a length-10 count of how many of each digit 0..9 appears and turn that tuple into the key, giving O(n d). A tuple is required, a list cannot be a dict key. One subtlety numbers add that letters…

Group numbers with the same digits

Your answer

More Coding questions