Trie vs Sorting for Prefix Search: When O(m) Beats O(m log n)

Someone decided to add autocomplete to your app. Congrats, now it's a data structures problem.

You have a list of words. A user types a prefix. You need to return every word that starts with it, preferably before they finish typing. Two approaches come to mind: sort the list and binary search for the boundary, or build a trie and walk down the nodes. The trie vs sorting tradeoff for prefix search is one of those decisions that looks obvious once you've made it wrong. The right choice comes down to one question: how many times are you searching?

How Both Approaches Actually Work

Sorting exploits something that falls out of lexicographic order for free: words sharing a prefix are adjacent in a sorted list. Sort once, then for each query find the left boundary with binary search and scan right until the prefix breaks.

import bisect

def prefix_search(words: list[str], prefix: str) -> list[str]:
    words.sort()
    left = bisect.bisect_left(words, prefix)
    results = []
    for word in words[left:]:
        if word.startswith(prefix):
            results.append(word)
        else:
            break
    return results

The sort costs O(n · m · log n), where n is the number of words and m is the average word length (each string comparison is O(m) in the worst case). Each subsequent prefix query costs O(m · log n) for the binary search plus O(k) to collect k results.

A trie stores every character of every word in a shared tree structure. Nodes branching from the same parent share a common prefix. Searching for a prefix means walking down the tree one character at a time. If you reach the end of the prefix, everything below is a match.

Build cost: O(n · m), one pass through every character. Query cost: O(m) to reach the prefix node, then a traversal of the subtree to collect matches. No log factor. No dependence on how many words exist. The corpus could have a million words and your query time doesn't care.

The Numbers, Side by Side

	Trie	Sort + Binary Search
Build	O(n · m)	O(n · m · log n)
Per prefix query	O(m + k)	O(m · log n + k)
Space (extra)	O(n · m) node objects	O(1) in-place sort
Multiple queries	O(Q · m) total	O(Q · m · log n) total

Where m is the average string length, n is the number of strings, k is the number of results returned, and Q is the number of queries.

For multiple queries against the same corpus, the trie compounds its advantage with every single search. The trie builds slower in practice due to pointer allocation overhead, but queries carry no log factor. For a single prefix query against an unsorted list, sorting is faster to implement and competitive in runtime.

A Concrete Problem: LeetCode 1268

LeetCode 1268 makes this tradeoff concrete. You get a list of products and a search word. For each prefix of the search word (1 character, 2 characters, all the way to the full word), return up to 3 lexicographically smallest products that start with that prefix.

The search word can be up to 1000 characters long. That's up to 1000 prefix queries against the same product list. One thousand. The problem is basically asking: "have you considered what this does at scale?"

Sort approach:

def suggestedProducts(products: list[str], searchWord: str) -> list[list[str]]:
    products.sort()
    results = []
    prefix = ""
    for char in searchWord:
        prefix += char
        left = bisect.bisect_left(products, prefix)
        bucket = []
        for product in products[left:left + 50]:  # scan right conservatively
            if product.startswith(prefix):
                bucket.append(product)
                if len(bucket) == 3:
                    break
        results.append(bucket)
    return results

Sort once, binary search per character. Total: O(n · m · log n) build plus O(|searchWord| · m · log n) for all queries.

Trie approach:

class TrieNode:
    def __init__(self):
        self.children: dict[str, TrieNode] = {}
        self.words: list[str] = []

def suggestedProducts(products: list[str], searchWord: str) -> list[list[str]]:
    products.sort()  # only to guarantee lexicographic order in results
    root = TrieNode()
    for product in products:
        node = root
        for char in product:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            if len(node.words) < 3:
                node.words.append(product)

    results = []
    node = root
    dead_end = False
    for char in searchWord:
        if dead_end or char not in node.children:
            dead_end = True
            results.append([])
        else:
            node = node.children[char]
            results.append(node.words)
    return results

The trie here stores the top-3 words at each node during build, which collapses query time to O(1) per prefix after walking to the node. The total query cost becomes O(|searchWord|). This is the trick that makes tries particularly powerful for suggestion systems: precompute the answers at construction time so query time is almost embarrassingly cheap.

For 1000 queries on a large product catalog, the trie is meaningfully faster. On LeetCode's test cases both pass, but the structural advantage compounds at scale.

When Sorting Actually Wins

Sorting is not just the naive fallback. It earns its keep. Here's when you should reach for it without apology.

One or a few queries. If you sort 10,000 words to answer a single prefix query, you paid O(n log n) upfront for something a trie would have built faster. The break-even is roughly when the query count Q satisfies Q · m · log n > n · m, which simplifies to Q > n. For far fewer queries than words, sorting wins. Nobody builds a trie for a one-off lookup.

Memory is the constraint. A trie node holds a pointer per possible character (26 for lowercase English, many more for Unicode). For a million-word corpus, the node allocations and pointer overhead can dwarf the sorted array. A sorted array is a contiguous block of memory the hardware prefetcher loves. Cache locality alone can make binary search faster than a theoretically superior trie for small to medium datasets. Theory says one thing. Your L1 cache says another. Listen to the cache.

You already have a sorted structure. If your data arrives sorted or you maintain a sorted set for other reasons (a B-tree index, a sorted set), binary search is free money. Building a trie on the side just to answer prefix queries is wasteful engineering.

You need to ship and not debug tries at 2am. Tries have fiddly edge cases: the end-of-word marker, correct subtree traversal, not double-counting words. Binary search on a sorted array is three lines of standard library code. In a time-pressured interview, the sort approach ships faster and breaks less. That is not a knock on tries. That is just physics.

When the Trie Wins

Repeated queries against the same corpus. Autocomplete, spell-check, IP routing tables, search bars. Every query costs O(m) regardless of corpus size. This is the canonical use case and tries are genuinely good at it.

You need more than just membership. Tries can store counts, aggregated values, or precomputed ranked results at each node. LeetCode 677 (Map Sum Pairs) and 745 (Prefix and Suffix Search) both exploit this. A sorted array forces you to reprocess for each new aggregation. Trie problems leave recognizable signals once you know what to look for.

Deletion is frequent. Deleting from a trie is O(m). Deleting from a sorted array is O(n) due to shifting. If your word list is dynamic and you're running prefix queries, the trie stays ahead over time.

Prefix counting without listing results. To count how many words start with "app" in a trie, walk to the "app" node and read the subtree count you stored during insertion. In a sorted array, you need two binary searches and a subtraction. The trie wins by a constant, but it's a real one. For how tries compare on non-prefix lookups, trie vs hash map covers the full picture.

Which One to Pick in an Interview

The question to ask yourself: am I building a system, or answering a single query?

If the interviewer says "design an autocomplete system," reach for the trie. The repeated-query pattern is implied, and the trie's architecture maps cleanly to the system design narrative: you build the index once, queries are cheap, you can attach frequency data to nodes. It tells a coherent story.

If the problem hands you a word list and asks for a one-shot prefix lookup, sorting is the cleaner first pass. Propose it, analyze the complexity, then ask whether the input could be queried multiple times. That one question shows the interviewer you understand the tradeoff without needing them to drag it out of you.

The deeper skill isn't knowing which structure is "better." It's recognizing which problem you're actually solving. Practice both on real problems with SpaceComplexity. The voice interview format forces you to articulate the tradeoff out loud, which is exactly what interviewers are listening for.