What is the Trie pattern?

The Trie pattern is a systematic approach to solving a class of coding interview problems. By recognizing the Trie structure, you can solve problems in optimal time complexity using proven techniques.

When should I use the Trie pattern?

Use the Trie pattern when the problem structure matches its recognition signals — typically when brute force would be O(n²) or worse, and the pattern reduces complexity to O(L) per operation, L = word length.

What is the time complexity of Trie?

The Trie pattern typically runs in O(L) per operation, L = word length time and uses O(N * L * 26) space. The exact complexity depends on the specific sub-variant being applied.

Is Trie important for coding interviews?

Yes — the Trie pattern is frequently tested at FAANG companies and competitive engineering interviews. Mastering this pattern gives you a reliable framework to solve many problem variations quickly.

How do I practice the Trie pattern?

Start by studying the pattern's mental model and recognition signals on DSAPatterns, then practice the curated LeetCode problems below in order from Easy to Hard. Aim for pattern recognition before memorizing solutions.

← back to patterns

pattern / MEDIUM

Trie.

Efficient prefix-based string operations

complexity

time

O(L) per operation, L = word length

space

O(N * L * 26)

practice questions

browse and solve all 0 pattern questions →

02' — visual

interactive

Sliding window — k = 3

Maximum sum subarray

Window

[0, 2]

Sum

Step

0 / 3

03'

mental
model.

Each node has 26 children (for lowercase). Path from root to marked node forms a word.

Trie is a tree-like data structure storing strings where each node represents a character. Enables fast prefix lookups.

when to use ✓

01Implement autocomplete
02Word search II
03Longest common prefix
04Word break

when not ✗

01Memory is critical
02Small alphabets

04'

recognition signals

Prefix matching

Word search in dictionary

Autocomplete

Word break problems

Standard TrieCompressed TrieSuffix Trie/TreeBitwise Trie

05'

templates

python

1# Beginner: Fixed-size sliding window
2def max_sum_k(nums, k):
3   n = len(nums)
4   if n < k:
5      return 0
6   window_sum = sum(nums[:k])
7   max_sum = window_sum
8   for i in range(k, n):
9      window_sum += nums[i] - nums[i - k]
10      max_sum = max(max_sum, window_sum)
11   return max_sum

common mistakes

01Memory issues with large inputs
02Confusing prefix vs word marker

interview tips

01Consider using hashmap of maps for sparse tries
02Combine with DFS for word search

06'

practice this pattern

0 curated problems from LeetCode

See all

No questions found for this pattern yet.

07'

faq

1# Beginner: Fixed-size sliding window

2def max_sum_k(nums, k):

3 n = len(nums)

4 if n < k:

5 return 0

6 window_sum = sum(nums[:k])

7 max_sum = window_sum

8 for i in range(k, n):

9 window_sum += nums[i] - nums[i - k]

10 max_sum = max(max_sum, window_sum)

11 return max_sum