Run it
Three approaches on the same input with their character comparisons counted, so "horizontal versus vertical" is a measurement rather than a preference.
Vertical scanning
Compare the same position across all strings, and stop at the first disagreement.
O(S) where S is the total number of characters, and O(1) extra space.
The two conditions in the inner if are both necessary: i >= len(other) catches a string that ends early, and other[i] != ch catches a mismatch. Omitting the length check raises IndexError on ["flower", "flow"], which is the most common bug here.
The early exit is what makes this fast in practice. If the first characters differ, it returns after one comparison, regardless of how long the strings are.
Horizontal scanning
Take the first string as a running answer, and shorten it against each subsequent string.
Same O(S) worst case. Slower in the bad case — the while loop can shorten one character at a time — but it reads clearly and startswith does the character comparison in C.
Both are acceptable answers. Vertical scanning exits earlier on the common case of an immediate mismatch; horizontal scanning is shorter. Being able to say which is better and why is what the comparison is for.
The two shortcuts worth knowing
Sort and compare the ends. After sorting lexicographically, the strings most unlike each other are first and last, so their common prefix is the answer for the whole list:
O(n log n · m) because of the sort — asymptotically worse, but the reasoning is neat and it is a legitimate answer if explained.
The os.path.commonprefix one-liner. The standard library has it, despite the misleading module:
It is a character-wise prefix, not path-aware — commonprefix(["/usr/lib", "/usr/local"]) returns "/usr/l", which is not a directory. For paths, os.path.commonpath is the correct function. Mention it after writing the loop.
The shrinking candidate
The answer is a prefix of every string, so it is certainly a prefix of the first one. Start there and remove characters as each new word disagrees. Because it only shrinks, no backtracking is possible and one pass is enough.
Two bounds to state: the answer is at most the length of the shortest string, and the total work is O(sum of all characters) in the worst case — usually far less, because the candidate collapses quickly on real input.
The sorting trick
Sort the list and compare only the first and last strings. In lexicographic order those two are the most different, so their common prefix is the whole list's. It is O(n log n·m) — worse asymptotically, and a nice observation to offer as an alternative rather than as the answer.
Vertical scanning, and tries
The other framing compares column by column: check index 0 across every word, then index 1, stopping at the first disagreement. Same complexity, and it exits earlier when the prefix is short and the strings are long.
If the question becomes "answer this repeatedly for many queries", the answer is a trie: insert every word, then walk down from the root while each node has exactly one child and ends no word. That is the structure this question is a warm-up for.
The trie approach
Insert every string into a trie, then walk down from the root while each node has exactly one child and is not the end of a word.
Overkill for a single query — building the trie costs O(S) and the scan is O(m), so it is no better than vertical scanning while using far more memory.
It becomes the right answer when the list is fixed and many prefix queries follow: autocomplete, prefix counting, finding all strings starting with a given prefix. If asked "what if I need to answer this repeatedly as strings are added?", the trie is the reason to bring it up.
The not node.is_end condition is easy to miss: for ["ab", "abc"] the answer is "ab", and the node after b marks the end of a word even though it still has one child.
| Approach | Time | Space | Use when |
|---|
| Vertical scan | O(S) | O(1) | Default |
| Horizontal scan | O(S) | O(1) | Slightly shorter code |
| Sort, compare ends | O(n log n · m) | O(n) | The reasoning is the point |
| Divide and conquer | O(S) | O(m log n) | Parallelisable |
| Trie | O(S) build, O(m) query | O(S) | Many queries |
| Binary search on length | O(S log m) | O(1) | Rarely |
Edge cases
| Case | Result |
|---|
| Empty list | "" — guard first, or strs[0] raises |
| One string | That string |
| Any empty string present | "" |
| All identical | The whole string |
| First character differs | "", after one comparison |
| One string is a prefix of the rest | That string |
| Unicode | Works per code point — see the caveat below |
The Unicode caveat is worth a sentence if the interviewer is interested: comparing code points means "café" written with a combining accent and "café" with a precomposed one share only "caf". Normalising with unicodedata.normalize("NFC", s) first fixes it. Rarely required, and knowing it exists is the signal.
Where it is used
- Autocomplete. Given the typed prefix, the common prefix of all matches can be filled in automatically — which is what shell tab-completion does.
- File path handling. Finding the common root directory of a set of paths, with
commonpath rather than commonprefix. - IP routing. Longest-prefix matching on address bits, implemented as a trie over bits.
- DNA sequence analysis, finding shared leading segments.
- URL routing in web frameworks, matching the longest registered path prefix.
- Compression. Front coding stores each string as a shared prefix length plus a suffix.
What it is testing
Do you guard the empty list? strs[0] on an empty list raises, and it is the first line of the solution.
Do you handle a short string? The i >= len(other) check, without which ["flower", "flow"] raises IndexError.
Can you compare approaches? Several are correct; choosing one and justifying it is the answer.
Do you spot the early exit? Vertical scanning returns after one comparison when the first characters differ.
Do you know when a trie earns its cost? Not for one query; yes for repeated prefix queries.
Recap in one screen
- Vertical scanning compares position by position across all strings and exits on the first mismatch — O(S) time, O(1) space.
- Check
i >= len(other) as well as inequality, or a shorter string raises IndexError. - Guard the empty list before touching
strs[0]. - Sorting and comparing only the first and last string works, at O(n log n · m).
- A trie is the right structure only when many prefix queries follow, not for one answer.