Trie vs Hash Map for Prefix Matching in DSA Typescript - Complexity Comparison

Time Complexity: Trie vs Hash Map for Prefix Matching

O(m) for Trie, O(n * m) for Hash Map

Understanding Time Complexity

We want to understand how fast we can find words that start with a certain prefix using two common data structures.

Which one works better as the list of words grows?

Scenario Under Consideration

Analyze the time complexity of prefix search using Trie and Hash Map.

// Trie prefix search
function trieStartsWith(root: TrieNode, prefix: string): boolean {
  let node = root;
  for (const char of prefix) {
    if (!node.children.has(char)) return false;
    node = node.children.get(char)!;
  }
  return true;
}

// Hash Map prefix search
function hashMapStartsWith(words: string[], prefix: string): boolean {
  for (const word of words) {
    if (word.startsWith(prefix)) return true;
  }
  return false;
}
    

The first checks prefix by walking down the Trie nodes. The second checks each word in the list one by one.

Identify Repeating Operations

Look at what repeats most in each method.

• Trie: Loop over prefix characters once.
• Hash Map: Loop over all words, then loop over prefix characters inside startsWith.
• Dominant operation: Hash Map loops over all words, which grows with number of words.

How Execution Grows With Input

Compare how work grows as we add more words or longer prefixes.

Input Size (words n)	Trie Operations	Hash Map Operations
10	Check prefix length (m) steps, e.g. 3	Check up to 10 words * prefix length
100	Still check prefix length (m) steps	Check up to 100 words * prefix length
1000	Still check prefix length (m) steps	Check up to 1000 words * prefix length

Pattern observation: Trie time depends mostly on prefix length, not number of words. Hash Map time grows with number of words.

Final Time Complexity

Time Complexity: O(m) for Trie, O(n * m) for Hash Map

Trie searches quickly by prefix length only. Hash Map checks every word, so it gets slower as word list grows.

Common Mistake

[X] Wrong: "Hash Map prefix search is always faster because hash lookups are quick."

[OK] Correct: Hash Map here stores full words, so prefix search still checks many words one by one, making it slower as list grows.

Interview Connect

Understanding these differences helps you choose the right tool for prefix search tasks, a common problem in coding interviews and real apps.

Self-Check

What if we stored all prefixes in the Hash Map instead of full words? How would that change the time complexity?