Coding Interview PatternsLongest Common Prefix
EasyTrie

Longest Common Prefix

Explanation & Solution

Practice Problem

Description

Given an array of strings strs, return the longest common prefix string amongst all strings in the array using a trie (prefix tree).

If there is no common prefix, return an empty string "".

Input:strs = ["flower","flow","flight"]
0
flower
1
flow
2
flight

Output: "fl"

Explanation: The longest common prefix shared by all three strings is "fl".

Constraints

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lowercase English letters.

Approach

Trie pattern

1. Build a Trie from All Strings

  • Create an empty trie root node
  • Insert every string from the array into the trie
  • At each node, track how many strings pass through it using a _count property
  • If any string is empty, immediately return "" since no common prefix exists

2. Traverse the Trie for Common Prefix

  • Start at the root node
  • At each level, check how many child keys exist (excluding metadata keys)
  • If there is exactly one child and its _count equals the total number of strings, that character is part of the common prefix
  • Append the character to the result and move to the child node

3. Stop When Branching Occurs

  • If a node has more than one child, the strings diverge at this point
  • If the single child's count is less than the total, not all strings share this character
  • Stop traversal and return the accumulated prefix

4. Return the Result

  • The prefix string built during traversal is the longest common prefix
  • If no common character was found, the result is an empty string

Key Insight

  • A trie naturally captures shared prefixes among strings. The common prefix corresponds to the path from the root where every node has exactly one child visited by all strings.
Time
O(S) where S is the sum of all characters in all strings
Space
O(S) for the trie structure

Solution Code

Previous
Word Break
Next
Stream of Characters