Группировка перестановок цифр

Задача

Дан массив целых неотрицательных чисел, нужно сгруппировать друг с другом числа, которые можно получить путём перестановки цифр их составляющих. Нули при этом игнорируем, т.к. нет числа 011. Решение должно быть максимально эффективно по памяти и времени.

Пример

console.log(digitPermutation([1230, 99, 23001, 123, 111, 300021, 101010, 90000009, 9]));
// [[99, 90000009], [111, 101010], [1230, 23001, 123, 300021], [9]]
console.log(digitPermutation([11, 22])); // [[11], [22]]
console.log(digitPermutation([11111111112, 12222222222])); // [[11111111112], [12222222222]]

Решение

Оптимальное решение

// Временная: O(n * d log d) — доминирует сортировка d. Сам проход по циклу занимает всего O(n)
// Пространственная: O(n * d)
//  В худшем случае (все числа уникальны по составу цифр) в Map будет N записей.
//  Ключи: Каждый ключ — это строка длиной до d. Суммарно: O(n * d)
 
function digitPermutation(nums) {
    const groups = new Map();
 
    for (const num of nums) {
        // 1. Превращаем в строку
        // 2. Выкидываем нули (replace)
        // 3. Разбиваем на массив, сортируем и собираем обратно (канонический ключ)
        const key = String(num)
            .replace(/0/g, '')
            .split('')
            .sort()
            .join('');
 
        // Если ключа нет — создаем новую группу
        if (!groups.has(key)) {
            groups.set(key, []);
        }
 
        // Добавляем число в соответствующую группу
        groups.get(key).push(num);
    }
 
    // Возвращаем массив групп
    return Array.from(groups.values());
}