Learn/TypeScript/13. Maps and sets in depth
Lesson 13 of 15
Sign in

TypeScript, lesson 13

Maps and sets in depth

Map and Set are the workhorses for questions like "how many of each?", "which items belong together?" and "what do these two lists have in common?". Their generic types, Map<K, V> and Set<T>, keep keys and values honest.

Counting

counts.get(w) has type number | undefined. The ?? 0 supplies a default for missing keys and also turns the type into a plain number, so the addition type-checks.

To print counts in order, spread the entries into an array of tuples and sort it:

2 exercises to try what you just read.

Exercise 1

Anagram groups

Press Ctrl Enter or Check to test your code.

Exercise 2

Allergy-safe menu

Press Ctrl Enter or Check to test your code.

Grouping

Grouping collects items under a key. With a Map<K, V[]>, create the list the first time you see a key:

Modern JavaScript also has this built in. Map.groupBy(items, fn) returns a Map from each key that fn returns to an array of matching items, and Object.groupBy returns a plain object instead (keys must be strings). TypeScript infers the key and item types from your callback:

Sets

A Set<T> holds each value at most once. add ignores duplicates, has checks membership quickly, and size counts the distinct values.

Set operations

Sets support the classic operations from maths as methods. Each returns a new Set:

Results keep insertion order, so sort them when the output order matters. Values are compared like ===: two different objects with the same contents count as different elements, so sets work best with strings and numbers.

Choosing the right structure

  • Need to look something up by a key? Map<K, V>.
  • Need to know only whether something is present? Set<T>.
  • Need order and duplicates? An array.

Choosing well makes code shorter and faster: set.has(x) takes the same time no matter how big the set is, while array.includes(x) checks elements one by one.

Further reading

  • MDN: Keyed collections
  • MDN: Set
  • MDN: Map.groupBy
  • TypeScript Handbook: Generics

Two words are anagrams when they use exactly the same letters, like listen and silent. The input is a list of lower-case words separated by spaces and/or line breaks. Group the anagrams together and print only the groups with two or more distinct words, one group per line, with the words of a group sorted alphabetically and separated by spaces. Order the groups by their first word. If there are no such groups, print none. A word repeated in the input counts once.

Sample input:

Sample output:

Hint: a word's signature is its letters sorted, [...word].sort().join(""). Anagrams share a signature, so use it as the key of a Map<string, Set<string>>.

The first input line lists a guest's allergies (ingredients separated by spaces). Every following line is a dish: NAME: INGREDIENT INGREDIENT .... For each dish, in input order, print NAME: safe if it contains none of the allergens, or NAME: contains X Y listing the allergens it contains in alphabetical order. Finally print safe dishes: N.

Use Set methods (isDisjointFrom, intersection) rather than nested loops.

Sample input:

Sample output:

const words = ["red", "blue", "red", "green", "red"];
const counts = new Map<string, number>();
for (const w of words) {
  counts.set(w, (counts.get(w) ?? 0) + 1);
}
// Map(3) { "red" => 3, "blue" => 1, "green" => 1 }
const ranked: [string, number][] = [...counts].sort((a, b) => b[1] - a[1]);
const byLength = new Map<number, string[]>();
for (const w of words) {
  const group = byLength.get(w.length);
  if (group) group.push(w);
  else byLength.set(w.length, [w]);
}
const grouped = Map.groupBy(words, (w) => w[0]);   // Map<string, string[]>
const unique = [...new Set(words)];   // ["red", "blue", "green"], first-seen order
const mine = new Set(["tea", "milk", "eggs"]);
const yours = new Set(["milk", "bread"]);

mine.union(yours);                // tea, milk, eggs, bread
mine.intersection(yours);         // milk
mine.difference(yours);           // tea, eggs
mine.symmetricDifference(yours);  // tea, eggs, bread
mine.isDisjointFrom(yours);       // false (they share milk)
mine.isSubsetOf(yours);           // false
listen enlist google silent
inlets banana
enlist inlets listen silent
nuts milk
pesto pasta: basil nuts cheese pasta milk
salad: lettuce tomato oil
pancakes: flour milk eggs
pesto pasta: contains milk nuts
salad: safe
pancakes: contains milk
safe dishes: 1