Topic: Learning notes

LeetCode 49: Group Anagrams in TypeScript, From Sorting Keys to Count Signatures

Work through a sorting-based Group Anagrams solution, its repeated-array-copy cost, and a count signature for the fixed lowercase alphabet.

I started by using each string’s sorted form as its group key. The idea is direct. Anagrams have the same sorted representation. The way a group is updated still changes the actual cost of the implementation.

Problem

Original problem: LeetCode 49: Group Anagrams

Given an array of lowercase English-letter strings, group the strings that are anagrams of one another. Neither group order nor order within a group is fixed.

Brute force compares groups again and again

One approach reads each string, scans the existing groups, and tests it against the first string in each group. If the test sorts both strings, one comparison costs O(k log k), where k is the maximum string length. When every string starts a new group, total time reaches O(n² × k log k).

The same strings are sorted and compared repeatedly. A key that represents a whole string avoids that repeated group scan.

My original sorting-key solution

function groupAnagrams(strs: string[]): string[][] {
  if (strs.length === 1) return [strs];

  const map = new Map<string, number[]>();

  for (let index = 0; index < strs.length; index += 1) {
    const sorted = strs[index].split("").sort().join("");

    if (map.has(sorted)) {
      map.set(sorted, [...map.get(sorted)!, index]);
    } else {
      map.set(sorted, [index]);
    }
  }

  const result: string[][] = [];

  map.forEach((indexes) => {
    result.push(indexes.map((index) => strs[index]));
  });

  return result;
}

This was my first solution. Each string becomes a character array, is sorted, and is joined back into a string. "eat", "tea", and "ate" all produce "aet", so that value works as a Map key. The value stores original indexes, which are later mapped back to strings.

The result is correct, but the strs.length === 1 early return is unnecessary. The general loop already returns [["a"]] or [[""]].

Cost in the original code

This line creates a new array whenever it sees the same key:

map.set(sorted, [...map.get(sorted)!, index]);

For a group with m strings, it copies index arrays of length 1, 2, through m - 1. That group adds O(m²) index copies. If every input string belongs to one group, the extra cost becomes O(n²). The original implementation therefore has worst-case time O(n × k log k + n²), not only the O(n × k log k) sorting cost.

This does not make the answer incorrect. It matters when a group becomes large.

A shorter version based on the original solution

Indexes and the final conversion are unnecessary. Store original strings in the group, then mutate the retrieved array with push().

function groupAnagramsBySorting(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();

  for (const str of strs) {
    const key = [...str].sort().join("");
    const group = groups.get(key);

    if (group) {
      group.push(str);
    } else {
      groups.set(key, [str]);
    }
  }

  return [...groups.values()];
}

push() changes the array that group references. It does not need to reset the Map value. With n strings and maximum length k, sorting each string takes O(n × k log k) under the usual interview model. Interview analysis normally treats Map access as expected O(1). Extra space for sorted keys and groups is O(n × k) in the worst case.

JavaScript does not require Array.prototype.sort() to use one fixed sorting algorithm or complexity. O(k log k) is the comparison-sort model used in interviews. MDN’s sort reference notes that actual complexity depends on the implementation.

Why push() becomes a number

These snippets do different things:

const indexes = map.get(key)!;
indexes.push(index);

map.set(key, map.get(key)!.push(index));

The first snippet keeps the array in the Map and changes its contents. The second writes push()’s return value back into the Map. push() returns the new array length, such as 2, rather than the array, so the value is overwritten with a number. MDN’s push() reference documents both the mutation and the new-length return value.

Typing the map as Map<string, string[]> also lets TypeScript reject an attempt to store a number. new Map() without type arguments loses that protection.

A count signature for the problem constraint

The problem limits every string to lowercase English letters. A key can therefore contain 26 counts. Equal letter counts create equal keys, without sorting each string.

function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();
  const firstLowercaseCode = "a".charCodeAt(0);

  for (const str of strs) {
    const counts = new Array<number>(26).fill(0);

    for (const char of str) {
      counts[char.charCodeAt(0) - firstLowercaseCode] += 1;
    }

    const key = counts.join("#");
    const group = groups.get(key);

    if (group) {
      group.push(str);
    } else {
      groups.set(key, [str]);
    }
  }

  return [...groups.values()];
}

Each key keeps counts for a through z. Creating it scans the string and handles 26 fixed values, so total time is O(Σ(|str| + 26)). Since 26 is fixed, interviews normally write this as O(n × k). This version fits the lowercase-English constraint only. For Unicode input, a sorting key or a Map frequency count is more general.

Correctness and loop invariant

For the sorting version, after processing strs[0..i], every groups entry maps a key to exactly the strings in that prefix whose sorted form equals that key.

The invariant holds before the loop because no strings have been processed. Each iteration computes the current string’s unique sorted key and either adds it to that key’s group or creates the group. After the loop, every input string appears in exactly one group. Two strings share a group exactly when their sorted forms match, which means they are anagrams.

The count-signature version follows the same proof. Its canonical key is the vector of 26 letter counts instead of the sorted string.

Minimal verification

LeetCode allows any output order, so the test sorts groups and their contents before comparing them.

import assert from "node:assert/strict";

function normalize(groups: string[][]): string[][] {
  return groups
    .map((group) => [...group].sort())
    .sort((left, right) => left.join(",").localeCompare(right.join(",")));
}

assert.deepStrictEqual(
  normalize(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])),
  normalize([["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]),
);
assert.deepStrictEqual(normalize(groupAnagrams([""])), [[""]]);
assert.deepStrictEqual(normalize(groupAnagrams(["a"])), [["a"]]);
assert.deepStrictEqual(
  normalize(groupAnagrams(["abc", "bca", "abc", "xyz"])),
  normalize([["abc", "bca", "abc"], ["xyz"]]),
);

Common mistakes

• Accumulating with map.set(key, [...old, value]). It is readable but repeatedly copies the existing group.
• Passing map.get(key).push(value) to map.set(). push() returns a numeric length.
• Keeping only sorted keys in a Set. A set detects a key but cannot keep the full group.
• Comparing nested output arrays without normalizing order. The problem permits any order.
• Reusing the 26-slot count array for Unicode input. That optimization depends on the lowercase-English constraint.

Transferable idea

When several values need grouping by the same structure, first choose a stable canonical key. A sorted string, character counts, a normalized URL, or a sorted ID set can serve that role. Once the key is stable, a single Map pass can build the groups.

References

• LeetCode 49: Group Anagrams: problem, examples, and lowercase-English constraint.
• MDN: Array.prototype.sort(): in-place sorting and implementation-dependent complexity.
• MDN: Map: key-value semantics and access-time requirement.
• MDN: Array.prototype.push(): in-place mutation and new-length return value.
• Node.js: assert.deepStrictEqual(): strict comparison for nested arrays.