Frequency Maps in Elixir: A Small Pattern with a Big Algorithmic Impact

Many algorithmic problems look unrelated at first.

Checking whether two words are anagrams, finding the most common event in a stream, validating whether a palindrome can be built from a string, or detecting a permutation inside a sliding window all appear to require different solutions.

But they often share the same underlying question:

How many times does each value appear?

That question leads to one of the most useful patterns in data structures and algorithms: the frequency map.

In Elixir, frequency maps are especially interesting because they show how a classic algorithmic technique fits naturally into an immutable, functional language.

What Is a Frequency Map?

A frequency map associates each distinct value with the number of times it occurs.

For example, the word "banana" can be represented as:

%{"a" => 3, "b" => 1, "n" => 2}

The original sequence contains six characters, but the map captures its essential composition. It tells us what is present and how often, while ignoring order.

That last detail is what makes frequency maps powerful. When order is irrelevant but quantity matters, a frequency map can turn a complicated comparison into a simple map equality check.

The Idiomatic Elixir Solution

Elixir provides Enum.frequencies/1, which builds a frequency map directly from any enumerable:

def frequency_map(string) do
  string
  |> String.graphemes()
  |> Enum.frequencies()
end

Calling it with "banana" produces:

frequency_map("banana")
# => %{"a" => 3, "b" => 1, "n" => 2}

String.graphemes/1 deserves attention here. A string in Elixir is a UTF-8 binary, not a collection of characters that can always be traversed safely one byte at a time. Converting it to graphemes makes the intention explicit and handles user-perceived characters more correctly.

For ASCII-only interview problems, String.to_charlist/1 may be slightly more compact and efficient. For real text handled by an application, graphemes are often the safer default.

Building It from First Principles

Convenience functions are useful, but understanding the mechanism matters. We can build the same map with Enum.reduce/3:

def frequency_map(string) do
  string
  |> String.graphemes()
  |> Enum.reduce(%{}, fn grapheme, frequencies ->
    Map.update(frequencies, grapheme, 1, &(&1 + 1))
  end)
end

The reduction starts with an empty map. For every grapheme:

1. If the key does not exist, Map.update/4 inserts it with the initial value 1.
2. If the key already exists, the update function increments its count.
3. The function returns a new map for the next iteration.

The important point is that no map is mutated in place. Each step produces a new logical state. Elixir's persistent data structures make this efficient by structurally sharing unchanged data instead of copying the entire map on every update.

This is a good example of how an imperative idea such as "increment this counter" becomes a data transformation in functional programming.

Anagrams Become Map Equality

Two words are anagrams when they contain exactly the same characters with exactly the same frequencies.

Once both words are converted into frequency maps, the algorithm becomes almost declarative:

defmodule Anagram do
  def anagram?(left, right) do
    frequencies(left) == frequencies(right)
  end

  defp frequencies(value) do
    value
    |> String.downcase()
    |> String.graphemes()
    |> Enum.reject(&(&1 == " "))
    |> Enum.frequencies()
  end
end

Examples:

Anagram.anagram?("BANANA", "AAANNB")
# => true

Anagram.anagram?("Elixir", "Erlang")
# => false

The normalization rules depend on the domain. Should spaces be ignored? What about punctuation or accents? Algorithmic exercises often avoid these questions, but production code cannot. A correct data structure does not compensate for unclear input semantics.

Complexity

If the input contains n graphemes, building the frequency map takes O(n) time because every element is visited once.

The map requires O(k) additional space, where k is the number of distinct graphemes. In the worst case, every grapheme is unique and k = n. When the alphabet is fixed and small, however, the practical memory usage is bounded.

For an anagram check involving two strings, the overall time remains O(n + m). This is better than sorting both inputs, which typically costs O(n log n + m log m).

Sorting can still be a perfectly reasonable solution, especially when clarity matters more than asymptotic performance. The key engineering skill is not memorizing one "correct" approach, but understanding the trade-off well enough to choose deliberately.

Beyond Anagrams

The same pattern appears in many problems:

• Palindrome construction: a string can be rearranged into a palindrome when at most one character has an odd frequency.
• Compression: repeated values can be represented by a value-count pair.
• Inventory and event aggregation: occurrences can be grouped by product, event type, status, or user.
• Duplicate detection: a count greater than one immediately identifies repetition.
• Cryptanalysis: character distributions can reveal patterns in encoded text.
• Sliding windows: a frequency map can track what enters and leaves a moving section of a sequence.

Sliding windows are particularly powerful when combined with frequency maps. Instead of rebuilding the counts for every substring, we update the map incrementally: add the element entering the window and remove the one leaving it.

Conceptually, the transition looks like this:

frequencies
|> Map.update(entering, 1, &(&1 + 1))
|> decrement_or_delete(leaving)

That combination often reduces a brute-force solution from quadratic time to linear time.

A Small Pattern That Changes How You See Problems

Frequency maps are simple. Their value comes from recognizing when a problem is really about identity and quantity rather than position.

Elixir makes that idea unusually clear. Pipelines expose the transformation, pattern-focused functions express intent, and immutable maps turn state changes into explicit values. The result is code that closely mirrors the reasoning behind the algorithm.

The next time a problem asks whether two collections contain the same elements, which value appears most often, or whether a moving range satisfies a constraint, ask one question first:

Would counting the elements make the structure of this problem visible?

Very often, the map is not just an implementation detail. It is the idea that unlocks the solution.