Hash Maps and Frequency Counting in JavaScript

A hash map stores values under keys and can find a key in constant time on average. In JavaScript that's usually a Map object, sometimes a plain object. The problems below use it to count how often something appears, or to remember what we've already seen so we don't have to search for it again.

It's worth trying when a problem asks about frequencies or "the same letters", or when the brute-force solution compares every element with every other one.

Problem 1: Anagram

Problem
Given two strings, a and b, write a function to determine if a is an anagram of b

Description

The function receives two strings and checks whether they are anagrams of each other. An anagram is a word or phrase formed by rearranging the letters of another, typically using all the original letters exactly once. The function should return true if the strings are anagrams, and false otherwise.

isAnagram("listen", "silent") // true
isAnagram("rat", "car")       // false

Assumptions

• inputs (string a and b) are lowercase for simplicity

Approach

1. One way of solving this involves converting each string into an array of characters, sorting these arrays, and then joining them back into strings. If the sorted strings are equal, then the original strings are anagrams.
2. Using a proper data structure like a hash map or an object to count the frequency of each character in the strings. Then, by comparing the character counts for both strings, you can determine if they are anagrams.

Solution 1: sort and compare

const isAnagram = (a, b) => a.split("").sort().join("") === b.split("").sort().join("")

Using the built-in functions available for strings/lists and piping the results we can get a readable solution. The cost is the sort, which is O(n log n).

Solution 2: count with a Map

function anagram(a, b) {
  let map = new Map();
  const aSpread = [...a];
  const bSpread = [...b];

  for (let i = 0; i < aSpread.length; i++) {
    if (map.has(aSpread[i])) {

      map.set(aSpread[i], map.get(aSpread[i]) + 1)
    } else {
      map.set(aSpread[i], 1)
    }
  }

  for (let i = 0; i < bSpread.length; i++) {
    if (map.has(bSpread[i])) {
      if (map.get(bSpread[i]) === 1) {
        map.delete(bSpread[i])
      } else {
        map.set(bSpread[i], map.get(bSpread[i]) - 1)
      }
    } else {
      return false
    }
  }
  return map.size === 0;

}

What I have done:

1. Spread the characters into an array so that it’s clear we’re working with a list. Then, create an empty hash map to store the character frequencies.
2. Loop over the first array (consisting of the string’s characters) and create a key for every unique character. Increment the count for each occurrence to track how many times each character appears.
3. In the second loop, iterate over the characters and subtract from the counts. The goal is to have a count of zero for each letter at the end. If a character is not found, return false.

If the two strings have different lengths they can't be anagrams, so an if (a.length !== b.length) return false at the top skips both loops.

Complexity

Here k is the number of distinct characters. With lowercase English letters it is at most 26, so the map itself takes constant space. The O(n) comes only from spreading the strings into arrays. Looping over the strings directly with for...of would avoid it and leave just the map.

If the inputs are small or performance isn't critical, the sorting one-liner is probably enough. For large inputs, prefer the hash map.

Problem 2: Two prices that match a gift card

Problem
You have a gift card worth target and a list of product prices. Find two different products whose prices add up to exactly target and return their positions in the list.

findPair([30, 15, 60, 45], 75) // [1, 2] → 15 + 60
findPair([25, 40, 25], 50)     // [0, 2] → 25 + 25

Assume there is exactly one valid pair, and a product can't be used twice.

The obvious way

Check every pair with two nested loops. It works, but for a list of n prices that is about n²/2 comparisons. With 10,000 products, that's 50 million checks.

Remember what you have seen

For each price, the partner we need is target - price. Instead of searching the rest of the list for it, keep a Map of the prices seen so far and their positions. Then "have I seen the partner?" is a single lookup.

function findPair(prices, target) {
  const seen = new Map() // price -> position in the list

  for (let i = 0; i < prices.length; i++) {
    const needed = target - prices[i]

    if (seen.has(needed)) {
      return [seen.get(needed), i]
    }

    seen.set(prices[i], i)
  }

  return null // no pair adds up to target
}

The order inside the loop matters. We look for the partner before storing the current price, so a product never pairs with itself. Two equal prices still work (25 + 25 in the second example), because the first 25 is already in the map when we reach the second one.

Walking through [30, 15, 60, 45] with target = 75:

Complexity

• Time: O(n). One pass over the list, and each has/get/set is O(1) on average.
• Space: O(n). In the worst case the pair is at the very end, and every other price is stored in the map first.

The nested loops need no extra memory, but they take O(n²) time.

Problem 3 (short): Group words that are anagrams

Problem
Given a list of words, put the words that are anagrams of each other in the same group.

groupAnagrams(["note", "tone", "cat", "act", "stone", "onset"])
// [["note", "tone"], ["cat", "act"], ["stone", "onset"]]

Instead of comparing two words, we need a key that comes out the same for every word in a group. Sorting the letters gives us one, since "note" and "tone" both become "enot". The Map goes from that key to the list of words with those letters.

function groupAnagrams(words) {
  const groups = new Map() // sorted letters -> words with those letters

  for (const word of words) {
    const key = [...word].sort().join("")

    if (!groups.has(key)) {
      groups.set(key, [])
    }
    groups.get(key).push(word)
  }

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

Sorting was the slower option in Problem 1, and it still costs O(k log k) for a word of k letters. For normal words that is cheap and the code stays short. If the words can be very long, the count-based key below avoids the sort.

Complexity

For n words of at most k letters:

• Time: O(n · k log k). Each word is sorted once.
• Space: O(n · k). Every word ends up stored in the map.

If the words only use lowercase letters, a key built from the 26 letter counts (for example "1,0,0,2,...") drops the time to O(n · k). The key is harder to read when you debug, though.

The pattern

Both ideas fit in a few lines of code:

// 1. Count: how many times does each value appear?
function countValues(values) {
  const counts = new Map()
  for (const value of values) {
    counts.set(value, (counts.get(value) ?? 0) + 1)
  }
  return counts
}

// 2. Remember: have I already seen the value I need?
// complement(value) returns the value that would complete it
function findMatch(values, complement) {
  const seen = new Map() // value -> position
  for (let i = 0; i < values.length; i++) {
    const needed = complement(values[i])
    if (seen.has(needed)) {
      return [seen.get(needed), i]
    }
    seen.set(values[i], i)
  }
  return null
}

// Problem 2 is findMatch(prices, price => target - price)

When the "value" is a group of things (like the letters of a word), build a key first and count or group by that key.

Takeaways

Part 2 is about two pointers. When the input is sorted, a pair like the one in Problem 2 can be found without a hash map, in O(1) extra space.

References

• MDN: Map
• MDN: Array.prototype.sort()
• MDN: Spread syntax