Longest Common Prefix
Problem statement
You're given an array of strings strs. Return the longest string that is a
prefix of every string in the array. If no non-empty prefix is shared by all
of them, return an empty string "".
Examples
Example 1
Input: strs = ["geeksforgeeks", "geeks", "geek", "geezer"]
Output: gee
Explanation: Every string starts with g, e, e — but the fourth
Example 2
Input: strs = ["apple", "ape", "april"]
Output: ap
Explanation: All three share a and p, but then diverge (p, e, and
Example 3
Input: strs = ["hello", "world"]
Output:
Explanation: The very first character already differs (h vs w), so
Hints
Approach
Optimal: Divide and conquer
approach above, just organized differently: each merge step compares two already-computed prefixes, and the merges together still touch each character at most a constant number of times.
for the recursion stack.
Intuition
Split the array of strings into two halves, and recursively find the longest common prefix of each half on its own. Once you have the left half's prefix and the right half's prefix, compare just those two against each other — the result is the common prefix for the whole array, since anything shared by both halves is shared by every string inside them. This is the same divide-and-merge shape as merge sort. Unlike the trie or the character-by- character approach, the two recursive halves here never need to look at each other's data until the final merge — so, unlike the other approaches, this one could have its two halves computed on separate machines or threads at the same time.
Steps
- If the current slice of the array holds just one string, that string is its own common prefix — return it directly.
- Otherwise, split the slice into a left half and a right half.
- Recursively find the common prefix of the left half (
p1) and the right half (p2). - Compare
p1andp2character by character and return their shared prefix. - The very first call, covering the whole array, produces the final answer.
For ["apple", "ape", "april"], the recursion splits, solves each leaf, and
merges back up:
Edge cases: a single-string array returns that string immediately, with no merging needed at all.
Complexity
Time O(n · m) - the same total amount of comparison work as the approach above, just organized differently: each merge step compares two already-computed prefixes, and the merges together still touch each character at most a constant number of times.
Space O(m) - for the prefix strings built along the way, plus O(log n) for the recursion stack.
class Solution:
def longestCommonPrefix(self, strs: list[str]) -> str:
def common_prefix(a: str, b: str) -> str:
min_len = min(len(a), len(b))
i = 0
while i < min_len and a[i] == b[i]:
i += 1
return a[:i]
def solve(lo: int, hi: int) -> str:
if lo == hi:
return strs[lo]
mid = (lo + hi) // 2
left = solve(lo, mid)
right = solve(mid + 1, hi)
return common_prefix(left, right)
return solve(0, len(strs) - 1)
if __name__ == "__main__":
print(Solution().longestCommonPrefix(["geeksforgeeks", "geeks", "geek", "geezer"])) # gee
print(Solution().longestCommonPrefix(["apple", "ape", "april"])) # ap
print(Solution().longestCommonPrefix(["hello", "world"])) # (empty string)RecapThe whole problem in a few lines, for the night before
- Spot it: the longest start shared by all strings in a list
- Idea: compare column by column across all strings and stop at the first mismatch or the end of the shortest string
- Cost: O(total characters) time, O(1) space
- Trap: an empty string in the list, or an empty list, gives an empty prefix
Interview follow-ups
What if the array is empty, or contains an empty string?
An empty string anywhere in the array forces the answer to be
""immediately, since the common prefix can never be longer than the shortest string in the array. An empty array has no strings to compare at all, so it needs to be handled as a special case before any of the approaches above run.How would you parallelize this across many machines?
The divide-and-conquer approach already splits the array into two halves that never need each other's data until the final merge step. That means each half — or each individual leaf — can be computed independently on a separate machine or thread, and only the merge step needs to wait for both sides to finish. It's the same shape as a distributed merge sort or a map-reduce reduce step.
What if you needed to repeatedly ask for the common prefix of different subsets of the same string array?
Build the trie once, up front, from every string in the array (the Better approach). Each subset's query then just walks down the same trie, but only follows the strings that belong to that subset, instead of rebuilding a structure from scratch for every query.
Frequently asked questions
Sorting places the two strings that differ the most from each other at the two extremes of the sorted order. Any prefix shared by every string in the array has to be shared by these two as well — if it weren't, it couldn't possibly be shared by everything in between them either.
Each one still has to look at every relevant character position of every string at least once in the worst case — that total amount of work doesn't go away. They differ only in how that work is organized: one pass over positions, a shared prefix tree, or a divide-and-merge split. None of them finds a way to look at fewer characters overall.
When the same set of strings needs many prefix-related queries answered against it — not just this one longest-common-prefix check. A trie, once built, is reusable: it's the same structure behind autocomplete suggestions and prefix-based routing tables, where the cost of building it once is paid back many times over.
Grouping config keys, log fields, or hostnames that share a naming
convention — like prod-web- or prod-api- — is a common step before
applying some rule to an entire group at once. Finding the shared prefix
across a set of names is exactly this problem.