Log inSign up
mediumGeeksforGeeksNot Started

Implement Phone Directory

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a list of contacts contact[] of size n where each contact is a string, and a query string s. Design a phone directory display suggestion mechanism where for each prefix s[0..i] of the search query (from length 1 to length of s), display all contacts in the directory that have s[0..i] as their prefix in alphabetical order. If no contact matches a prefix, output 0 or an empty list for that prefix.

Example 1 · Example 1: Standard contact directory:

Input: contact = ["geeikistest", "geeksforgeeks", "geeksfortest"], s = "gee"
Output: [["geeikistest", "geeksforgeeks", "geeksfortest"], ["geeikistest", "geeksforgeeks", "geeksfortest"], ["geeikistest", "geeksforgeeks", "geeksfortest"]]
Explanation: All 3 contacts start with g, ge, and gee. Trie Structure: (root) | g | e | e / \ i k ... ...

Constraints:

  • 1 <= n <= 100
  • 1 <= |contact[i]| <= 50
  • 1 <= |s| <= 100
  • All contacts and query string s consist of lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Implement a phone directory / autocomplete engine using a Trie.
  • Traverse Trie children in lexicographical order to eliminate explicit sorting.
  • Maintain continuous prefix pointer state across incremental keystroke queries.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Interactive search suggestion query for every prefix of a typing user.
  • Results must be displayed in sorted alphabetical order.
  • Contacts are static or pre-populated; multiple incremental prefix queries.

Algorithmic Decision Tree:

  • Use a Trie where each node has children[26] and boolean isEnd.
  • Walk down the Trie character by character for query string s.
  • At each node, trigger an in-order DFS ('a' to 'z') to collect suggestions.

Connected Patterns:

Search Suggestions SystemAutocomplete SystemPrefix Matching

1. Linear Scan and Sort for Each Prefix

Intuition

For each prefix length k from 1 to |s|, loop over all words in contact. If word.substr(0, k) == s.substr(0, k), add to unique set. Sort the collected words and append to results.

When to apply: Quick brute force baseline.

Algorithm

  1. Step 1: Loop k from 1 to s.length().
  2. Step 2: Prefix pref = s.substr(0, k).
  3. Step 3: Collect all unique contacts starting with pref.
  4. Step 4: Sort collected list alphabetically and add to results.
  5. Step 5: If list is empty, append {"0"} or empty list.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <set>
5#include <algorithm>
6using namespace std;
7
8class Solution {
9public:
10 vector<vector<string>> displayContacts(int n, string contact[], string s) {
11 vector<vector<string>> result;
12 set<string> uniqueContacts(contact, contact + n);
13
14 string pref = "";
15 for (char c : s) {
16 pref += c;
17 vector<string> matched;
18 for (const string& word : uniqueContacts) {
19 if (word.rfind(pref, 0) == 0) { // startsWith
20 matched.push_back(word);
21 }
22 }
23 if (matched.empty()) matched.push_back("0");
24 result.push_back(matched);
25 }
26 return result;
27 }
28};
29
30int main() {
31 Solution sol;
32 string contacts[] = {"geeksforgeeks", "geeksfortest", "geeikistest"};
33 string s = "gee";
34 auto res = sol.displayContacts(3, contacts, s);
35 for (size_t i = 0; i < res.size(); i++) {
36 cout << "Prefix '" << s.substr(0, i + 1) << "': ";
37 for (const string& w : res[i]) cout << w << " ";
38 cout << endl;
39 }
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(|s| * N * L log N) — Repeats filtering and sorting for each prefix of the query string.
  • Space complexity: O(N * L) — Stores contacts and output suggestion lists.

Why Brute Force Doesn't Scale:

With 50,000 contacts and 20 keystrokes, linear scan performs 1,000,000 string checks.

Trie advances 1 pointer per keystroke and only explores the relevant subtree, running in less than 5ms.

2. Sorted Array Binary Search Bounds

Intuition

Deduplicate and sort unique contacts. For each prefix, binary search finds the first word starting with prefix. Scan forward until words no longer start with prefix.

When to apply: When memory overhead of Trie nodes must be avoided.

Algorithm

  1. Step 1: Sort unique contacts lexicographically.
  2. Step 2: For prefix pref, binary search for first word >= pref.
  3. Step 3: Collect all consecutive words starting with pref.
  4. Step 4: Append list to result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<string>> displayContacts(int n, string contact[], string s) {
10 vector<string> sortedContacts;
11 {
12 vector<string> temp(contact, contact + n);
13 sort(temp.begin(), temp.end());
14 temp.erase(unique(temp.begin(), temp.end()), temp.end());
15 sortedContacts = move(temp);
16 }
17
18 vector<vector<string>> result;
19 string pref = "";
20 for (char c : s) {
21 pref += c;
22 auto it = lower_bound(sortedContacts.begin(), sortedContacts.end(), pref);
23 vector<string> matched;
24 while (it != sortedContacts.end() && it->rfind(pref, 0) == 0) {
25 matched.push_back(*it);
26 ++it;
27 }
28 if (matched.empty()) matched.push_back("0");
29 result.push_back(matched);
30 }
31 return result;
32 }
33};
34
35int main() {
36 Solution sol;
37 string contacts[] = {"geeksforgeeks", "geeksfortest", "geeikistest"};
38 string s = "gee";
39 auto res = sol.displayContacts(3, contacts, s);
40 for (size_t i = 0; i < res.size(); i++) {
41 cout << "Prefix '" << s.substr(0, i + 1) << "': ";
42 for (const string& w : res[i]) cout << w << " ";
43 cout << endl;
44 }
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N * L log N + |s| * (log N + K)) — Sorting takes O(N * L log N). Each prefix takes O(log N) binary search plus O(K) output collection.
  • Space complexity: O(N * L) — Stores sorted contact array.

3. Trie with Lexicographical Subtree Traversal

Intuition

Insert contacts into Trie. Walk query string s. At each step, if child exists, move pointer. Perform DFS visiting children 0 through 25, automatically yielding suggestions in alphabetical order. If at any step child does not exist, all remaining longer prefixes produce 0.

When to apply: Standard optimal solution for phone directories and autocompletes.

Algorithm

  1. Step 1: Define TrieNode with children[26] and boolean isEnd.
  2. Step 2: Insert all contacts into Trie.
  3. Step 3: Track curr = root. Maintain boolean matched = true.
  4. Step 4: For each char in s: if curr != null && curr.children[char - 'a'] != null, move curr = curr.children[char - 'a'].
  5. Step 5: If valid, run DFS from curr storing accumulated words into suggestion list.
  6. Step 6: If curr == null, append {"0"}.

Interactive Prefix Search Trace for Query 'ge'

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Process char 'g'
Visual state
Values and pointers at this exact step
tree
Root
(root)
prefix 'g'
'g'
branch 'e'
'e'
branch 'f'
'f'

Node order shown; add connections to display explicit tree edges.

curr: g
Check / comparison
root.children['g'] exists
Decision / next transition
Collect suggestions for prefix 'g': ['geeks', 'gfg'].
Why this step matters

Step 1: Process char g. Root has child g. DFS from g visits geeks and gfg.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6struct TrieNode {
7 TrieNode* children[26];
8 bool isEnd;
9 TrieNode() : isEnd(false) {
10 for (int i = 0; i < 26; i++) children[i] = nullptr;
11 }
12};
13
14class Solution {
15 TrieNode* root;
16
17 void insert(const string& word) {
18 TrieNode* curr = root;
19 for (char c : word) {
20 int idx = c - 'a';
21 if (!curr->children[idx]) curr->children[idx] = new TrieNode();
22 curr = curr->children[idx];
23 }
24 curr->isEnd = true;
25 }
26
27 void dfs(TrieNode* node, string& path, vector<string>& suggestions) {
28 if (!node) return;
29 if (node->isEnd) suggestions.push_back(path);
30
31 for (int i = 0; i < 26; i++) {
32 if (node->children[i]) {
33 path.push_back('a' + i);
34 dfs(node->children[i], path, suggestions);
35 path.pop_back();
36 }
37 }
38 }
39
40public:
41 vector<vector<string>> displayContacts(int n, string contact[], string s) {
42 root = new TrieNode();
43 for (int i = 0; i < n; i++) insert(contact[i]);
44
45 vector<vector<string>> result;
46 TrieNode* curr = root;
47 string prefix = "";
48 bool noMatch = false;
49
50 for (char c : s) {
51 prefix += c;
52 int idx = c - 'a';
53
54 if (!noMatch && curr && curr->children[idx]) {
55 curr = curr->children[idx];
56 vector<string> suggestions;
57 string path = prefix;
58 dfs(curr, path, suggestions);
59 result.push_back(suggestions);
60 } else {
61 noMatch = true;
62 curr = nullptr;
63 result.push_back({"0"});
64 }
65 }
66 return result;
67 }
68};
69
70int main() {
71 Solution sol;
72 string contacts[] = {"geeksforgeeks", "geeksfortest", "geeikistest"};
73 string s = "gee";
74 auto res = sol.displayContacts(3, contacts, s);
75 for (size_t i = 0; i < res.size(); i++) {
76 cout << "Prefix '" << s.substr(0, i + 1) << "': ";
77 for (const string& w : res[i]) cout << w << " ";
78 cout << endl;
79 }
80 return 0;
81}

Time & Space Complexity

  • Time complexity: O(N * L + |s| * 26 * L) — Building Trie takes O(N * L). Each prefix DFS visits matching subtree paths bounded by remaining letters.
  • Space complexity: O(N * L * 26) — Trie nodes allocate up to 26 pointers each.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Full Contact List FilteringO(|s| * N * L log(N))O(N * L)For each prefix s[0..i], loop through all N contacts, check if contact.startsWith(prefix), deduplicate and sort.Linear scan and re-sorting of N contacts on every prefix.
2.Better — Sorted Array with Binary Search RangeO(N * L log N + |s| * (log N + K))O(N * L)Sort unique contacts alphabetically. For each prefix, find lower and upper bounds using binary search.String comparison cost during binary search.
3.Optimal — Trie with Lexicographical Subtree DFSOptimalO(N * L + |s| * K * L)O(N * L * 26)Insert contacts into Trie. Walk query prefix iteratively. Run DFS from the prefix node visiting children in a-z order.None. Industry standard for search autocomplete and phone directories.

Common Pitfalls & Crucial Edge Cases

Restarting Trie traversal from root on each keystroke

Re-walking from root takes O(|s|^2) instead of maintaining the pointer in O(|s|).

Sorting output arrays explicitly

Iterating children 0..25 in DFS naturally provides alphabetical order for free.

Forgetting to mark `noMatch = true`

Attempting to read curr.children[idx] on a null pointer causes crash.

Crucial Edge Cases to Validate:

  • No matching contact for query prefix — Must return 0 or empty list as specified.
  • Duplicate contacts in input — Insert into a Set first to avoid emitting duplicate suggestions.
  • Query longer than any contact — Once prefix fails, all subsequent longer queries also return 0 in O(1).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Point out that traversing children in order 0 to 25 guarantees alphabetical results with zero sorting overhead.
  2. Explain the performance boost of caching the Trie node pointer across keystrokes as the user types.
  3. Discuss how this pattern forms the foundation of real-world search engines and phone dialers.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does traversing Trie children from 0 (a) to 25 (z) guarantee alphabetical output?

2.If query prefix abc does not exist in the Trie, what is the best way to handle abcd?

Back to DSA Sheet