Autocomplete System with Trie in DSA Java - Time & Space Complexity

Time Complexity: Autocomplete System with Trie

O(n)

Understanding Time Complexity

We want to understand how fast the autocomplete system works as we add more words or search for prefixes.

Specifically, how does the time to find suggestions grow when the input size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isWord = false;
}

void insert(TrieNode root, String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        int index = c - 'a';
        if (node.children[index] == null) {
            node.children[index] = new TrieNode();
        }
        node = node.children[index];
    }
    node.isWord = true;
}
    

This code inserts a word into a Trie, letter by letter, creating nodes as needed.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character of the input word.
• How many times: Once for each letter in the word (length n).

How Execution Grows With Input

As the word length grows, the number of steps grows directly with it.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The time grows linearly with the length of the word.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert a word grows directly with the word's length.

Common Mistake

[X] Wrong: "The time depends on the total number of words already in the Trie."

[OK] Correct: Insertion only depends on the length of the word being added, not how many words are stored.

Interview Connect

Understanding this helps you explain how tries efficiently handle prefix searches and insertions, a common real-world problem.

Self-Check

"What if we changed the Trie to store words with uppercase letters and digits? How would the time complexity change?"

Practice

1. What is the main purpose of using a Trie in an autocomplete system?

easy

A. To count the frequency of words

B. To efficiently store and search prefixes of words

C. To sort words alphabetically

D. To encrypt the stored words

Solution

1. Step 1: Understand the role of Trie in prefix search

   A Trie is a tree-like data structure that stores characters of words in a way that common prefixes share nodes.

2. Step 2: Connect Trie usage to autocomplete

   Autocomplete requires quick lookup of words starting with a given prefix, which Trie supports efficiently.

3. Final Answer:

   To efficiently store and search prefixes of words -> Option B

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is built for prefix-based fast search [OK]

Common Mistakes:

• Confusing Trie with sorting data structure
• Thinking Trie encrypts data
• Assuming Trie counts word frequency only

2. Which of the following is the correct way to declare a Trie node class in Java?

easy

A. class TrieNode { char[] children = new char[26]; boolean isWord; }

B. class TrieNode { int[] children = new int[26]; boolean isWord; }

C. class TrieNode { String[] children = new String[26]; boolean isWord; }

D. class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isWord; }

Solution

1. Step 1: Identify the correct data type for children nodes

   Each child should be a reference to another TrieNode, so an array of TrieNode objects is needed.

2. Step 2: Check other options for correctness

   Options B, C, and D use primitive types or String arrays which cannot represent child nodes properly.

3. Final Answer:

   class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isWord; } -> Option D

4. Quick Check:

   Children = TrieNode array [OK]

Hint: Children must be TrieNode references, not primitives [OK]

Common Mistakes:

• Using int or char arrays instead of TrieNode array
• Using String array for children
• Forgetting to initialize children array

3. What will be the output of the following Java code snippet using a Trie for autocomplete?

Trie trie = new Trie();
trie.insert("dog");
trie.insert("deer");
trie.insert("deal");
List<String> results = trie.autocomplete("de");
System.out.println(results);

medium

A. ["deer", "deal"]

B. ["dog", "deer", "deal"]

C. ["dog"]

D. []

Solution

1. Step 1: Understand inserted words and prefix search

   Words inserted are "dog", "deer", and "deal". The prefix searched is "de".

2. Step 2: Filter words starting with prefix "de"

   Only "deer" and "deal" start with "de"; "dog" starts with "do".

3. Final Answer:

   ["deer", "deal"] -> Option A

4. Quick Check:

   Autocomplete("de") = ["deer", "deal"] [OK]

Hint: Autocomplete returns words starting exactly with prefix [OK]

Common Mistakes:

• Including words not matching prefix
• Returning empty list by mistake
• Confusing prefix "de" with "do"

4. Identify the bug in this Trie insertion method snippet and select the fix:

public void insert(String word) {
  TrieNode node = root;
  for (int i = 0; i <= word.length(); i++) {
    char c = word.charAt(i);
    int index = c - 'a';
    if (node.children[index] == null) {
      node.children[index] = new TrieNode();
    }
    node = node.children[index];
  }
  node.isWord = true;
}

medium

A. Change loop condition to i < word.length() to avoid IndexOutOfBoundsException

B. Initialize root inside the loop

C. Remove node.isWord assignment

D. Change char c to int c

Solution

1. Step 1: Analyze loop boundary

   The loop runs from i = 0 to i <= word.length(), which causes i to reach word.length(), an invalid index for charAt.

2. Step 2: Fix loop condition

   Changing condition to i < word.length() prevents IndexOutOfBoundsException by stopping before invalid index.

3. Final Answer:

   Change loop condition to i < word.length() to avoid IndexOutOfBoundsException -> Option A

4. Quick Check:

   Loop index < word.length() [OK]

Hint: Loop over string chars with i < length, not <= length [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Ignoring IndexOutOfBoundsException
• Misunderstanding charAt indexing

5. You want to extend a Trie-based autocomplete system to return suggestions sorted by frequency of word usage. Which data structure modification is best to support this efficiently?

hard

A. Store words in a linked list attached to each node

B. Sort all words alphabetically after each insertion

C. Store a frequency count at each word node and use a priority queue during search

D. Use a hash map to store words and frequencies separately from the Trie

Solution

1. Step 1: Understand frequency tracking in Trie nodes

   Storing frequency count at each word node allows tracking how often each word is used.

2. Step 2: Use priority queue to get top frequent words during autocomplete

   During prefix search, a priority queue can efficiently retrieve words with highest frequency.

3. Final Answer:

   Store a frequency count at each word node and use a priority queue during search -> Option C

4. Quick Check:

   Frequency + priority queue = efficient sorted suggestions [OK]

Hint: Use frequency counts + priority queue for sorted autocomplete [OK]

Common Mistakes:

• Sorting all words after each insertion (inefficient)
• Separating frequency from Trie nodes (loses prefix efficiency)
• Using linked list for sorting (slow access)